以下是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;} 2206855 2007-01-24 13:21:44 Accepted 1638 C++ 00:01.47 11072K Crux.D
评论