被成为经典的双塔问题。痛恨死了,我搞了好多天,我真是对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; }
这题我好早都看了,不会…
看看这个滚动数组…
不会 求解释,看了几个解题报告还是不明白 = =#