ZOJ 2059 —— The Twin Towers 解题报告

据说很经典的DP题目。来源浙大月赛。

参考解题资料：http://allen303allen.bokee.com/viewdiary.19263200.html

?

自己的代码：

/*ZOJ 2059 —— The Twin Towers给定一个数字序列，问能不能构成2个序列，使得这两个序列的和相同，序列中的数字可以不用完。输出构成的2个序列的最大长度。对于每个数字有3种选择，要么不放，要么放到较低的塔上，要么放到较高的塔上。那么状态怎么表示呢？看到题目中塔的最大高度为2000，如果枚举这三种情况加100个数据就是3^100，肯定gg了。从别人那学到的一种表示状态的方法，可以将2000看做最大高度差，那么共有2001个状态了。对于每个状态的定义就是在高度差为i的情况下，较高的塔的高度是多少。对于在高度差一定时，可以选择将当前数字添加到较高的塔上还是较低的塔上，然后就是结果，如果添加到较低的塔上会有2种情况：1. 还是比高塔低   2. 比高塔高了 ， 更新新的高度差下的最大塔高， 向高塔中添加此数，可以正常更新。状态转移方程：h[i]为第i个数字，dp[i][j]为用到第i个数字时，高度差为j时较高的塔的高度     dp[i][j+h[i]] = max(dp[i][j+h[i], dp[i-1][j] + h[i]); //向高塔上添加此数。     if ( h[i] > j ) //h[i]比高度差j大，所以添加h[i]后就比dp[i-1][j]里的最高塔还高了。        dp[i][h[i]-j] = max(dp[i][h[i]-j], dp[i-1][j] + h[i]-j);    else           //h[i]比高度差j小 ，所以添加h[i]后较高的塔还较高，         dp[i][j-h[i]] = max(dp[i][j-h[i]], dp[i-1][j] ); 做的时候运用循环数组，节省空间，注意初始化，在j高度差下，没有数字时要初始化成一个状态。 */#include <iostream>#include <cstdio>int max(const int a, const int b){    if ( a > b )        return a;    else        return b;}int min(const int a, const int b){    if ( a > b )    return b;    else    return a;} int main(){    int dp[2][2001], a[101];    int n, i, j;    int sum ;    int t;    while ( scanf("%d", &n ) != EOF && n != -1 )    {        sum = 0;        for ( i = 1; i <= n; ++i )        {                scanf("%d", &a[i]);            sum += a[i];        }        sum = min(sum, 2000);        for ( i = 0; i <= sum; ++i )            dp[0][i] = -1;        dp[0][0] = 0;        dp[0][a[1]] = a[1];        t = 0;        for ( i = 2; i <= n; ++i )        {            t = 1-t;            for ( j = 0; j <= sum; ++j )                dp[t][j] = -1;            for ( j = 0; j <= sum; ++j )            {                dp[t][j] = max(dp[t][j], dp[1-t][j]);                if ( dp[1-t][j] == -1 )                    continue;                if ( j + a[i] <= sum ) //加到高的tower上                     dp[t][j+a[i]] = max(dp[1-t][j]+a[i], dp[t][j+a[i]]);                     if ( j >= a[i] ) //加到低的上面比高的低                 {                    dp[t][j-a[i]] = max(dp[t][j-a[i]], dp[1-t][j]);                }                else //加到低的上面比高的高                 {                    dp[t][a[i]-j] = max(dp[t][a[i]-j], dp[1-t][j] + a[i]-j);                 }                            }                    }                                     if ( dp[t][0] > 0 )            printf("%d\n",dp[t][0]);        else            printf("Sorry\n");          }    return 0;}

?

?