最近几天在研究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;} 2238803 2007-02-18 16:04:42 Accepted 2059 C++ 00:00.30 2988K Crux.D

评论