1.http://blog.csdn.net/Miracle_ma/article/details/51495549（大牛详解）
2.惭愧，想了很久也没想出来状态应该怎么表达。dp[2][|hA-hB|]:当A和B的高度之差为J时的所用的积木的高度。
3.滚动数组不是很明白。果然我很弱~~~
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 using namespace std; 6 7 const int maxn=500005; 8 9 int T,n; 10 int dp[2][maxn],a[55]; 11 12 int main() 13 { scanf("%d",&T); 14 while(T--){ 15 scanf("%d",&n); 16 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 17 memset(dp,-1,sizeof(dp)); 18 dp[0][0]=0; 19 int cur=0; 20 for(int i=1;i<=n;i++){ 21 cur^=1; 22 for(int j=0;j<=500000;j++){ 23 dp[cur][j]=max(dp[cur][j],dp[cur^1][j]); 24 if(j+a[i]<=500000&&dp[cur^1][j+a[i]]!=-1) dp[cur][j]=max(dp[cur][j],dp[cur^1][j+a[i]]+a[i]); 25 if(j-a[i]>=0&&dp[cur^1][j-a[i]]!=-1) dp[cur][j]=max(dp[cur][j],dp[cur^1][j-a[i]]+a[i]); 26 if(j-a[i]<0&&dp[cur^1][a[i]-j]!=-1) dp[cur][j]=max(dp[cur][j],dp[cur^1][a[i]-j]+a[i]); 27 } 28 } 29 if(dp[cur][0]==0) printf("GG\n"); 30 else printf("%d\n",dp[cur][0]/2); 31 } 32 return 0; 33 } 34
原文：http://www.cnblogs.com/zgglj-com/p/6929756.html