Vijos P1037 解题报告

starli posted @ 2015年6月07日 09:44 in 动态规划 , 129 阅读

第一次看到这个题目,第一个反应是两次背包,第一次背包之后取走用过的,然后再取一次背包,但是这个做法不但麻烦,还有点bug。

然后想到,以水晶划分阶段,f[i][j]表示第一座塔高度为i,第二座塔高度为j的情况是否可以达到,每一块水晶有三种决策(1)不放(2)加到第一座上(3)加到第二座上。于是就可以用dp做了,初始化为f[0][0]=true;

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int f[2001][2001],i,j,k,n,h[101],big=0,Max;


int main(){
	//freopen("1037.in","r",stdin);freopen("1037.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		 scanf("%d",&h[i]);
	f[0][0]=true;
	for(i=1;i<=n;i++){
		for(j=big;j>=0;j--)
		  for(k=big;k>=0;k--)
		  	if(f[j][k]){f[j+h[i]][k]=true;f[j][k+h[i]]=true;big=max(j+h[i],big);big=max(big,k+h[i]);}
	}
	/*
	for(i=0;i<=big;i++){
		for(j=0;j<=big;j++)
			printf("%d ",f[i][j]);
		printf("\n");
	}*/
	for(i=1;i<=1000;i++) if(f[i][i]) Max=i;
	if(!Max) printf("Impossible");
	else printf("%d\n",Max);
	return 0;
}

 


登录 *


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