题意：
\(n\)个木块放到两个塔里，每个木块可放可不放，使得两塔高度相同且高度最大，求最大高度。
这个差值
\(DP\)的思维难度还是很大的，没想出来，我就打了一个
\(dfs\)骗了好像
\(20\)还是
\(30\)分吧（看来搜索也写挂）。
正解是
\(DP\)，
\(f[i][j]\)表示前
\(i\)块木块使得两个塔的高度差为
\(k\)时高度最大的那个是什么
（神奇的状态） 那么无非就
\(4\)种情况：
1、第
\(i\)块不放：
\(f[i][j]=f[i-1][j]\) 2、第
\(i\)块放到矮的上面，矮的仍然矮：
\(f[i][j]=f[i-1][j+a[i]]\) 3、第
\(i\)块放到高的上面，高的当然高：
\(f[i][j]=f[i-1][j-a[i]]+a[i]\) 4、第
\(i\)块放到矮的上面，矮的变高的：
\(f[i][j]=f[i-1][a[i]-j]+j\) 可以发现，
\(f[i]\)的取值仅与
\(f[i-1]\)有关，于是第一维是可以滚掉的。
#include #include #define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);#define Close fclose(stdin);fclose(stdout);const int MAXN = 55;const int MAX = 500010;int dp[MAX][2];inline int max(int a, int b){ return a > b ? a : b;}int n, s[MAXN], sum;int main(){ Open("tower"); scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &s[i]), sum += s[i]; memset(dp, 128, sizeof dp); dp[0][0] = dp[0][1] = 0; for(int i = 1; i <= n; ++i) for(int j = sum; ~j; --j){ dp[j][i%2] = dp[j][!(i%2)]; if(j + s[i] <= sum) dp[j][i%2] = max(dp[j][i%2], dp[j + s[i]][!(i%2)]); if(j - s[i] >= 0) dp[j][i%2] = max(dp[j][i%2], dp[j - s[i]][!(i%2)] + s[i]); if(j < s[i]) dp[j][i%2] = max(dp[j][i%2], dp[s[i] - j][!(i%2)] + j); } printf("%d\n", !dp[0][n%2] ? -1 : dp[0][n%2]); Close; return 0;}