10
18
2015
0

[BZOJ1618] [Usaco2008 Nov] Buying Hay 购买干草

最近感觉颓废指数直线上升。所以为了每日一以上题解,我又来做大水题了。

这题是一个完全背包,令初始的价格为负然后按照正常完全背包处理即可。

#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;
}
Category: BZOJ | Tags: bzoj | Read Count: 619

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com