第一次看到这个题目,第一个反应是两次背包,第一次背包之后取走用过的,然后再取一次背包,但是这个做法不但麻烦,还有点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; }