DZY 's BLOG - Hello World!

BZOJ2748: [HAOI2012]音量调节【背包】

原来省选题也有裸背包啊、、

if (F[i-1][j]) then F[i][j+c[i]]=F[i][j-c[i]]=1

好了水掉了

#include<cstdio>
int f[52][1005]={0},n,st,ed,c[52];
int main(){
    scanf("%d%d%d",&n,&st,&ed); for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    f[0][st]=1;  for(int i=1;i<=n;i++)   for(int j=0;j<=ed;j++){
        if(!f[i-1][j])  continue;
        if(j+c[i]<=ed)  f[i][j+c[i]]=1;
        if(j-c[i]>=0)   f[i][j-c[i]]=1;
    }int An;    for(An=ed;~An;An--) if(f[n][An]) break; printf("%d\n",An);
}