http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1059
经典的DP,不会做啊 (╬ ̄皿 ̄)凸
。。。。。。。。。。。
设dp[j]表示高度差为j时,矮塔的高度。
对于每个块x,只有两种放法,1)放到高塔上 2)放到矮塔上
采用滚动数组,维护两个一维数组就可以了。
Code:
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define min(a,b) a<b ? a:b #define max(a,b) a>b ? a:b using namespace std; const int H = 2000; int dp[2][2010];//dp[][j]表示高度差为j时,矮塔的高度。 int x; int main() { int n, i, j, t; while(scanf("%d",&n)&&n!=-1) { memset(dp,-1,sizeof(dp)); dp[0][0] = 0; for(i=1,t=0; i<=n; i++) { t = 1-t; scanf("%d",&x); for(j=0; j<=H; j++) if(dp[1-t][j]!=-1) { //更新高度差为j时,矮塔的高度 dp[t][j] = max(dp[1-t][j], dp[t][j]); //把高为x的块加到高塔上 if(j+x<H) dp[t][j+x] = max(dp[t][j+x], dp[1-t][j]); //把高为x的块加到矮塔上 if(j>=x)//加到矮塔的上面比高塔的低 dp[t][j-x] = max(dp[t][j-x], dp[1-t][j]+x); else //加到矮塔的上面比高塔的高 { dp[t][x-j] = max(dp[t][x-j], dp[1-t][j]+j); } } } if(dp[t][0]>0) printf("%d\n",dp[t][0]); else printf("Sorry\n"); } return 0; }