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

dzy posted @ 2013年6月08日 21:31 in BZOJ with tags BZOJ 背包 , 1406 阅读

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

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);
}
Avatar_small
ekhan.in 说:
2023年6月08日 20:36

Our team is made up of professional writers and citizen journalists with a wide range of journalism interests who are passionate about reporting Education Updates with transparency in the general public interest.ekhan is a group of ekhan.in professional writers who have banded together to provide devoted news coverage of current events in India. Our team is made up of professional writers and citizen journalists with a wide range of journalism interests who are passionate about reporting Education Updates with transparency in the general public interest.


登录 *


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