求解一维背包为什么过不了,答案全偏大
  • 板块P1717 钓鱼
  • 楼主lht1217
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/8 08:20
  • 上次更新2023/11/8 14:29:49
查看原帖
求解一维背包为什么过不了,答案全偏大
743734
lht1217楼主2023/11/8 08:20

P1717

#include<bits/stdc++.h>
using namespace std;
#define N 30
#define il inline
#define ll long long
il int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48; ch=getchar();}
    return x*f;
}
il void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int n,h;
int f[N],d[N],t[N]; 
int dp[200];
il int cal(int x,int k){
	return k*f[x]-d[x]*k*(k-1)/2;
}
int main(){
	n=read(); h=read()*12;//同时 /5。
	for(int i=1;i<=n;i++) f[i]=read();
	for(int i=1;i<=n;i++) d[i]=read();
	for(int i=2;i<=n;i++) t[i]=read();
	memset(dp,~0x3f,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++)
		for(int j=h;j>=t[i];j--)//从后枚举。
			for(int k=0;k+t[i]<=j&&(k-1)*d[i]<f[i];k++)
				dp[j]=max(dp[j],dp[j-t[i]-k]+cal(i,k));
	int ans=0;
	for(int i=1;i<=h;i++) ans=max(ans,dp[i]);
	write(ans);
	return 0;
}

2023/11/8 08:20
加载中...