ZOJ 2059 The Twin Towers (DP)

ZOJ 2059 The Twin Towers

被成为经典的双塔问题。痛恨死了，我搞了好多天，我真是对dp一点都不开窍啊。。怎么办?看了大黄的思路，dp[i]表示高度差为i时候低的塔的最大值，这个状态定义的很纠结，也不是很好理解。就先拿我的代码来说吧，每输入一个水晶，就更新一下dp。。。这个时候我们需要一个额外的t数组来保存前边所有物品所产生的状态，因为只用一个dp来保存的话，当前物品所产生的状态有可能叠加。。对状态的更新产生影响。。t数组每次更新完就再赋给dp。。dp[0]表示高度相等时的高度。。。

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>

using namespace std;

int main(void)
{
	int dp[2001],t[2001];
	int N,x,i;
	while( cin >> N && N != -1 ){
		memset( dp,-1,sizeof(dp) );
		memset( t,-1,sizeof(t) );
		dp[0] = t[0] = 0;
		while( N-- ){
			cin >> x;
			for( i = 0; i <=2000; i++ ){
				if( dp[i] != -1 ){
					if( i + x <= 2000 )
						t[i+x] = max( t[i+x],dp[i] );
                                        //加到高度高的塔上
					if( x < i )
						t[i-x] = max( dp[i]+x,t[i-x] );
                                        //这两个表示x加到高度低的上
					else
						t[x-i] = max( dp[i]+i,t[x-i] );

				}
			}
			memcpy(dp,t,sizeof(t));
		}
		if( dp[0] != 0 ) cout << dp[0] << endl;
		else cout << "Sorry" << endl;
	}
	return 0;
}