有点意思的DP题，同样也有不小的难度。

模型大致如下：一组背包，除了体积以外，还有重量的限制。有3种不同的item：比如说一把剑，一件盔甲，一双鞋。他们各自有体积，重量，Def值，而组合到一起——也许叫做不死斗篷，出题者明显是英雄无敌的爱好者——又有新的Def加成。如何得到最大的Def？

对于每一辆车（背包），在装满的情形下，可以得到几组不同的xyz，代表三种装备的数量。假如能够得到所有车子总的xyz组合，这题就迎刃而解了。但是我们不能对100辆车子，对每种xyz之和进行搜索，这样数据量太大。

考虑到题目给出xyz<500，故而建立m[i][x][y]的数组，对前i辆车中的xy进行DP。因为在当前i车中，对于每组ix iy，都有唯一对应的iz（最大）。而只要把这辆车中的ixiy去掉就是前一辆车i-1下的xyz值，所以m[i][x][y] =MAX（m[i - 1][x - ix][y - iy]+iz），ix iy 遍历，表示在前i辆车中z能达到的最大值。从而所有的xyz组合都被记录下来了。这种用N-1维数组记录一个N维组合，然后对其DP求得最后一个数的方法就很棒。

为了节省空间，采用滚动数组。具体代码中把i-1提前，对于i-1下每一组xy，加上这辆车里的ixiy就是当前i组下的xy。

#include <cstdio>
#include <string>

#define min(x, y) ( x < y ? x : y )
#define rg(x, y) ( x = ( y > x ? y : x ) )  //replace if greater

int N, c1, c2, c3, def, w[100], s[100], m[2][501][501], cs;
int wa, sa, da, wb, sb, db, wc, sc, dc, mx, my;

int init ();
void dp ();
void print ();
void test ( int );

int main ()
{
    //freopen ( "in.txt", "r", stdin );
    cs = 0;
    while ( init () )
    {
        dp ();
        print ();
    }
    return 0;
}

int init ()
{
    scanf ( "%d", &N );
    if ( !N )
    {
        return 0;
    }
    int i;
    scanf ( "%d%d%d", &wa, &sa, &da );
    scanf ( "%d%d%d", &wb, &sb, &db );
    scanf ( "%d%d%d", &wc, &sc, &dc );
    scanf ( "%d%d%d%d", &c1, &c2, &c3, &def );
    for ( i = 0; i < N; i ++ )
    {
        scanf ( "%d%d", &w[i], &s[i] );
    }
    def -= c1 * da + c2 * db + c3 * dc;
    memset ( m, 0xff, sizeof ( m ) );
    return N;
}

void dp ()
{
    int i, x, y;
    int rw, rs;
    mx = 0, my = 0;
    m[0][0][0] = 0;
    for ( i = 0; i < N; i ++ )
    {
        memset ( m[1], 0xff, sizeof ( m[1] ) );
        int ix, iy, iz, mmx, mmy;
        mmx = mx, mmy = my;
        for ( x = 0; x <= mx; x ++ )
        {
            for ( y = 0; y <= my; y ++ )
            {
                if ( m[0][x][y] != -1 )
                {
                    for ( ix = 0; wa*ix <= w[i] && sa*ix <= s[i]; ix ++ )
                    {
                        rw = w[i] - wa * ix, rs = s[i] - sa * ix; 
                        for ( iy = 0; iy*wb <= rw && iy*sb <= rs; iy ++ )
                        {
                            iz = min ( ( rw - iy * wb ) / wc, ( rs - iy * sb ) / sc );
                            rg ( m[1][x + ix][y + iy], iz + m[0][x][y] );
                            rg ( mmx, x + ix );
                            rg ( mmy, y + iy );
                        }
                    }
                }
            }
        }
        mx = mmx, my = mmy;
        memcpy ( m[0], m[1], sizeof ( m[1] ) );
        //test ( i );
    }
}

void print ()
{
    int ans = 0, t;
    int x, y, z;
    for ( x = 0; x <= mx; x ++ )
    {
        for ( y = 0; y <= my; y ++ )
        {
            z = m[0][x][y];
            if ( z != -1 )
            {
                t = da * x + db * y + dc * z;
                rg ( ans, t );
                int c = min ( min ( x / c1, y / c2 ), z / c3 );
                if ( def > 0 )
                {
                    t += def * c;
                }
                rg ( ans, t );
            }
        }
    }
    if ( cs ++ )
    {
        printf ( "\n" );
    }
    printf ( "Case %d: %d\n", cs, ans );
}

评论