最近感觉颓废指数直线上升。所以为了每日一以上题解，我又来做大水题了。
这题是一个完全背包，令初始的价格为负然后按照正常完全背包处理即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,v,c[5005],f[500005],w[5005];
int main(){
freopen("1618.in","r",stdin);
freopen("1618.out","w",stdout);
scanf("%d %d",&n,&v);
for(int i=1;i<=n;i++){scanf("%d %d",&w[i],&c[i]);c[i]=-c[i];}
memset(f,-127,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++){
for(int j=w[i];j<=v+5000;j++){
f[j]=max(f[j],f[j-w[i]]+c[i]);
//printf("%d %d %d",f[j],j,f[j-w[i]]+c[i]);
}
}
for(int i=v+1;i<=v+5000;i++)f[v]=max(f[v],f[i]);
printf("%d\n",-f[v]);
return 0;
}
评论 (0)
