经典双塔dp---zoj_2059

题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2059

????????? 题目大意是：给定n个立方体，去组成2个塔高度相同的塔，求能组成的双塔的最大高度是多少，立方体不必用完。

??????状态dp[i][j]为读取第i个立方体，双塔高度差为j时的，较高塔的高度的最大值。

???? 显然dp[i][j]读取第i个立方体时有3中情况：

???? 1）即不放在较高的塔上，也不放在较低的塔上

???? 2）放在较高的塔上

???? 3）放在较低的塔上,分两中情况，1.低塔的高度超过高塔，2.低塔的高度还是低于高塔

???? 对应上述三中情况对应的状态转换是

???? 1）dp[i][j]=max(dp[i-1][j],dp[i][j]);

???? 2) dp[i][j]=max(dp[i-1][j-h[i]]+h[i],dp[i][j]);(注意，必须j>h[i])

???? 3) 1.dp[i][j]=max(dp[i-1][h[i]-j]+j,dp[i][j]);(注意，必须j<h[i])

??????? 2.dp[i][j]=max(dp[i-1][j+h[i]],dp[i][j]);

???? 最后注意边界处理！！

zoj_2059.cpp:

????

?