BZOJ2748 [HAOI2012]音量调节 【动态规划初步】

tonyfang posted @ 2015年8月23日 19:42 in BZOJ with tags c++ OI , 264 阅读

原来有写过这个题解的吧,应该在20150815常州培训填坑的时候。

具体就看代码吧,挺简单的啦。

 

# include <stdio.h>
int n,maxl,minl,beg;
int c[51];
bool pd[51][1010];
int main() {
	scanf("%d%d%d",&n,&beg,&maxl);
	for (int i=1;i<=n;++i) scanf("%d",&c[i]);
	pd[0][beg]=1;
	for (int i=1;i<=n;++i)
		for (int j=0;j<=1000;++j) {
			if(j-c[i]>=minl) pd[i][j]=pd[i][j]||pd[i-1][j-c[i]];
			if(j+c[i]<=maxl) pd[i][j]=pd[i][j]||pd[i-1][j+c[i]];
		}
	bool flag=1;
	for (int i=maxl;i>=0;--i)
		if(pd[n][i]) {
			printf("%d\n",i);
			flag=0;
			break;
		}
	if(flag) printf("-1\n");
	return 0;
}

登录 *


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