dp[i][j]: 代表合理利用前i個水晶建造兩座塔，較高的塔比較低的塔高j時，較高的塔的高度。 每次轉移考慮三種情況，不選用第i個，或者分別放在較高的塔上、較低的塔上。
#include<bits/stdc++.h>using namespace std;int sum,n,h[1000],dp[2][5000];int main(){ while(~scanf("%d",&n)) { sum=0; memset(dp,0xff,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d",&h[i]); sum+=h[i]; } int now=0; dp[0][0]=0; for(int i=1;i<=n;i++) { now=now^1; for(int j=0;j<=sum;j++) { dp[now][j]=dp[now^1][j]; } for(int j=0;j<=sum;j++) { if(dp[now^1][j]!=-1) dp[now][j+h[i]]=max(dp[now][j+h[i]],dp[now^1][j]+h[i]); if(j<=h[i]&&dp[now^1][j]!=-1) dp[now][h[i]-j]=max(dp[now][h[i]-j],dp[now^1][j]-j+h[i]); if(j>h[i]&&dp[now^1][j]!=-1) dp[now][j-h[i]]=max(dp[now][j-h[i]],dp[now^1][j]); } //for(int j=0;j<=sum;j++)新聞熱點
疑難解答
