以下是xavier_lt的解题报告。
稍微分析一下，不难发现O(nabc)的DP方程：
f[0,0,0]=0;
f[i,j,k]=max{ f[i-1,j,k] + attack[i+j+k], f[i,j-1,k] + defence[i+j+
k], f[i,j,k-1] + special[i+j+k] }这样，求总的属性值只要加一个第二关键
字c[i,j,k]就可以了。但是通过题目，发现N是一个很大的数，于是用这种方法将
会非常慢!
但是，很显然有一些牌是可以完全忽略掉的，就像[0,0,0]这样的牌。要怎么删掉
一定不需要的牌呢？令S=a+b+c，则对于每种属性，只需要前S张即可了，而总计
只需要3S<=300张牌。这样优化后，算法的速度就会大大的提高了，优化后的时间
复杂度是
O(nlgn+min(n,3s)*a*b*c)。
-------------------------------------------------------------------
我只看的懂这些了。但是这个办法真的很经典，一道难题就这样变成了O(1004)的
简单题。
-------------------------------------------------------------------
进一步分析，此题的总属性值不会超过300*100，个体属性值不会超过100*100，
所以，可以建立一个二分图来解决此题。令左边为N个红节点（攻击属性），N个
黄节点（防御属性），N个蓝节点（特殊属性），右边是A+B+C个节点，第I个红节
点到第J个右节点的边权为Attack[I]*100000+Attack[I]+Defence[I]+Special
[I]，同理建立其他颜色的左节点到每个右节点的边。这样我们只需对这个二分图
求最大全匹配就可以了，复杂度将会下降到O(nlgn+min(n,3s)*(a+b+c)^2)，优
化后的时间还是很不错的^_^。

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

#define S 102
#define SS 100001

int opt[S][S][S], sum[S][S][S], n, a[SS], b[SS], c[SS], s[SS], num[SS], used[SS], total;
int cs, numa, numb, numc;

bool cmp_a ( const int &i, const int &j )
{
 return a[i] == a[j] ? s[i] > s[j] : a[i] > a[j];
}

bool cmp_b ( const int &i, const int &j )
{
 return b[i] == b[j] ? s[i] > s[j] : b[i] > b[j];
}

bool cmp_c ( const int &i, const int &j )
{
 return c[i] == c[j] ? s[i] > s[j] : c[i] > c[j];
}

void pre ()
{
 total = numa + numb + numc;
 int i;
 memset ( used, 0, sizeof (used) );
 for ( i = 0; i < n; i ++ )
  num[i] = i;
 sort ( num, num + n, cmp_a );
 for ( i = 0; i < total; i ++ )
  used[num[i]] = 1;
 sort ( num, num + n, cmp_b );
 for ( i = 0; i < total; i ++ )
  used[num[i]] = 1;
 sort ( num, num + n, cmp_c );
 for ( i = 0; i < total; i ++ )
  used[num[i]] = 1;
 memset ( opt, -1, sizeof (opt) );
 memset ( sum, 0, sizeof (sum) );
 opt[0][0][0] = sum[0][0][0] = 0;
}

void dp ()
{
 int i, k, j, t, ta, tb, tc, tsum;
 for ( t = 0; t < n; t ++ )
 {
  if ( used[t] )
  {
   for ( i = numa; i >= 0; i -- )
   {
    for ( k = numb; k >= 0; k -- )
    {
     for ( j = numc; j >= 0; j -- )
     {
      if ( opt[i][k][j] != -1)
      {
       tsum = s[t] + sum[i][k][j];

       ta = a[t] + opt[i][k][j];       
       if ( ta > opt[i + 1][k][j] || ( ta == opt[i + 1][k][j] && tsum > sum[i + 1][k][j] ) )
       {
        opt[i + 1][k][j] = ta;
        sum[i + 1][k][j] = tsum;
       }

       tb = b[t] + opt[i][k][j];
       if ( tb > opt[i][k + 1][j] || ( tb == opt[i][k + 1][j] && tsum > sum[i][k + 1][j] ) )
       {
        opt[i][k + 1][j] = tb;
        sum[i][k + 1][j] = tsum;
       }

       tc = c[t] + opt[i][k][j];
       if ( tc > opt[i][k][j + 1] || ( tc == opt[i][k][j + 1] && tsum > sum[i][k][j + 1] ) )
       {
        opt[i][k][j + 1] = tc;
        sum[i][k][j + 1] = tsum;
       }
      }
     }
    }
   }
  }
 }
 printf ( "%d %d\n", opt[numa][numb][numc], sum[numa][numb][numc] );
}

int main ()
{
 //freopen ( "in.txt", "r", stdin );
 scanf ( "%d", &cs );
 while ( cs -- )
 {
  scanf ( "%d", &n );
  scanf ( "%d %d %d", &numa, &numb, &numc );
  int i;
  for ( i = 0; i < n; i ++)
  {
   scanf ( "%d %d %d", a + i, b + i, c + i );
   s[i] = a[i] + b[i] + c[i];
  }
  pre ();
  dp ();
 }
 return 0;
}

评论