2756964 2008-02-21 18:12:06 Accepted 1013 C++ 00:03.02 2404K C.D.=.= 有点意思的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 greaterint 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 );}

评论