[VIJOS P1037]搭建双塔

danihao123 posted @ 2016年8月21日 16:11 in 题解 with tags Vijos 动态规划 , 151 阅读
转载请注明出处:http://danihao123.is-programmer.com/

很不错的题啊……

很容易想到构造三维的状态,但无论时间还是空间都不好。我们可以构造[tex]f[i][delta][/tex]这种状态,表示用前[tex]i[/tex]块水晶,搭建出的双塔高度差为[tex]delta[/tex]时较大塔的高度。显然答案为[tex]f[n][0][/tex]。

转移的时候,要考虑放到高塔上还是低塔上,以及是否会导致高低塔地位对调。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=101,maxV=2001;
int d[2][maxV];
int V[maxn];
int main(){
	int n,maxj=0;
	register int i,j,now,pre;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&V[i]);
		maxj+=V[i];
	}
	memset(d,-1,sizeof(d));
	d[0][0]=0;
	for(i=1;i<=n;i++){
		now=i%2;
		pre=1-now;
		for(j=0;j<=maxj;j++){
			if(d[pre][j]>=0)
				d[now][j]=d[pre][j];
			if(V[i]<=j){
				if(d[pre][j-V[i]]>=0){
					d[now][j]=max(d[now][j],d[pre][j-V[i]]+V[i]);
				}
			}
			if(V[i]>j && d[pre][V[i]-j]>=0){
				d[now][j]=max(d[now][j],d[pre][V[i]-j]+j);
			}
			if(j+V[i]<=maxj && d[pre][j+V[i]]>=0)
				d[now][j]=max(d[now][j],d[pre][j+V[i]]);
		}
	}
	if(d[1&n][0]<=0)
		puts("Impossible");
	else
		printf("%d\n",d[1&n][0]);
	return 0;
}

登录 *


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