BZOJ 2748 [HAOI2012]音量调节

starli posted @ 2016年2月01日 17:26 in 动态规划 , 98 阅读

看起来是个傻逼题

定义f[i][j]表示第i个节目音量能否为j ,则f[i][j]= f[i-1][j+c[i]] || f[i-1][j-c[i]]。最后扫一下f[n]里面的最大值

滚动数组都不用开就过了

 代码

#include <cstdio>
#include <algorithm>
using namespace std;
int n,bl,ml,a[55],ans=0;
bool f[55][1010];
int main(){
	// freopen("2748.in","r",stdin);freopen("2748.out","w",stdout);
	scanf("%d%d%d",&n,&bl,&ml);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	f[0][bl]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=ml;j++) {
			if(j-a[i]>=0 && f[i-1][j-a[i]]) f[i][j]=1;
			if(j+a[i]<=ml && f[i-1][j+a[i]]) f[i][j]=1;
		}
	for(int i=ml;i>=0;i--) if(f[n][i]) {printf("%d",i);ans=1;break;}
	if(!ans) printf("-1");
	return 0;
}

登录 *


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