最近几天在研究usaco，那是一个很有趣的地方，做起题来像通关游戏，所以zoj倒做得少了。不有趣的地方是一旦一道题解不出，就像碰到一位大Boss，死打也不扣血，非得你跑到城外去拼命练级方可过关。于是回过头来写写以前没做出的几道简单dp题，这就是其一。

题目的大意如下：有一列N个水晶，把他们搭成双子塔，要求塔高一样，求塔的最大高度。当初做的时候不小心看错了条件，以为每块水晶最大高度是2000，接着开了个200000的数组，自己机子都过不了。今天看了busycai的程序，才明白搞错了。总高度是2000，所以O(n) = N×2000.时间还算不错。

起初想用b[i]来表示塔高为i的某种状态（塔高之差？或是别的什么），结果想了半天不得其解。其实把设定倒过来，当bi表示塔高之差为i的时候，对总高度dp，这样就简单了。

对0<= i <= 2000，当在左或右边放入a[k]之后，差有两种可能，i + a[k], i - a[k]。然后更新，即可。

#include <cstdio>
#include <string>

int abs ( int i )
{
    return i > 0 ? i : -i ;
}

int N, a[101], b[2][2001], p;

int main ()
{
    //freopen ( "in.txt", "r", stdin );
    while ( scanf ( "%d", &N ) && N >= 0 )
    {
        int i, end, j, k;
        for ( i = 0; i < N; i ++ )
        {
            scanf ( "%d", &a[i] );
        }
        memset ( b, -1, sizeof ( b ) );
        b[1][0] = 0, p = 0, end = 0;
        for ( i = 0; i < N; i ++, p = 1 - p )
        {
            memcpy ( b[p], b[1 - p], sizeof ( b[p] ) );
            end += a[i];
            for ( j = 0; j <= end; j ++ )
            {
                k = abs ( j + a[i] );
                if ( k <= end && b[1 - p][j] >= 0 && b[p][k] < b[1 - p][j] + a[i] )
                {
                    b[p][j + a[i]] = b[1 - p][j] + a[i];
                }
                k = abs ( j - a[i] );
                if ( k <= end && b[1 - p][j] >= 0 && b[p][k] < b[1 - p][j] + a[i] )
                {
                    b[p][k] = b[1 - p][j] + a[i];
                }
            }   
        }
        if ( b[1 - p][0] )
        {
            printf ( "%d\n", b[1 - p][0] / 2 );
        }
        else
        {
            printf ( "Sorry\n" );
        }
    }
    return 0;
}

评论