UVa 1508 - Equipment | Sengxian's Blog

UVa 1508 - Equipment

#暴力 #状态压缩

Published on 2016-01-20

描述

给出 $n(n\le 10000)$ 件装备，每个装备有 $5$ 个属性 $(r_{1}, r_{2}, r_{3}, r_{4}, r_{5})$ 。定义同时挑选多件装备的效果是每个属性都为挑选的装备中最大的那个，现在要挑选 $k(1\le k\le n)$ 件装备，问所能得到的 $5$ 个属性的和最大是多少？

样例输入

2
4 2
30 30 30 30 0
50 0 0 0 0
0 50 0 50 10
0 0 50 0 20
5 1
10 20 60 0 0
0 0 20 50 30
30 50 20 20 0
10 10 10 20 30
30 0 20 10 20

样例输出

170
120

附加输入

1
3 2
50 50 50 50 60
30 30 40 50 70
50 50 60 50 30

附加输出

分析

首先很关键的一点就是，如果选择 $k \ge 5$ 件装备，那么直接取 $5$ 种属性每种最大的那个，加起来就行了。关键在于 $k < 5$ 的时候。
原本我的想法是贪心，只选一件的情况肯定是选和最大的，然后看再选哪个收益最大，但这显然是错的，选一件和选两件是完全不同的情况，所以这样贪心肯定是不正确的（附加输入就体现了这一点）。
所以，对于每一件装备，我们试着这样思考：枚举每一个属性是否作为最终方案中这一个属性的最大值，我们可以用 $5$ 个二进制位来表示是否作为最大值。例如 $11111$ 表示这件装备的五个属性全部作为最终方案的最大值。而 $10101$ 则是第 1、3、5 个属性作为最终方案的最大值。总共只有 $2^{5} - 1 = 31$ 种状态，可以接受。接着处理出每一种状态的被选中属性和（注意这还是针对这一件物品）。
对所有装备维护一个数组 $\mathrm{maxSum}[s]$ ， $s$ 表示刚刚的状态。 $\mathrm{maxSum}[s]$ 表示在所有物品处于状态 $s$ 时，最大的被选中属性和。我们可以知道最终方案是的属性一定是由各个装备合并而来，那么我们就要枚举，看看最终方案的每个属性是由哪一件物品而来的。于是最终方案可以表示为状态 $11111$ ，那么我们就是要寻找 $k$ 个子集，且 $k$ 个子集合并起来正好是 $11111$ ，每一个子集表示一个物品提供某些属性的最大值。答案就是这 $k$ 个子集的 $\mathrm{maxSum}$ 之和。
但有没有可能这 $k$ 个子集不一定恰好代表 $k$ 件装备呢？不用担心，我们算出的答案一定是最优的，如果不足 $k$ 个，随便挑选几件对答案没有影响。
如何枚举子集，方法很巧妙，记住就行，参见代码。

代码

//  Created by Sengxian on 1/19/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1508 暴力
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
const int maxn = 10000 + 3, maxk = 5;

inline int ReadInt() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    do {
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(isdigit(ch));
    return x;
}

struct equipment {
    int val[maxk];
}s[maxn];
int n, k;

int maxSum[1 << maxk], mem[1 << maxk][maxk];

int dfs(int S, int k) {
    if(S == 0 || k == 0) return 0;
    if(mem[S][k] != -1) return mem[S][k];
    int sub = S, ans = maxSum[S];
    do {
        if(sub != S && sub) ans = max(ans, dfs(S - sub, k - 1) + maxSum[sub]);
        sub = (sub - 1) & S;
    }while(sub != S);
    return mem[S][k] = ans;
}

int main() {
    int caseNum = ReadInt();
    while(caseNum--) {
        n = ReadInt(), k = ReadInt();
        if(k >= maxk) {
            int st[maxk] = {0};
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < maxk; ++j) st[j] = max(st[j], ReadInt());
            int sum = 0;
            for(int i = 0; i < maxk; ++i) sum += st[i];
            printf("%d\n", sum);
        }else {
            memset(maxSum, 0, sizeof(maxSum));
            memset(mem, -1, sizeof(mem));
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < maxk; ++j) s[i].val[j] = ReadInt();
                for(int S = (1 << maxk) - 1; S > 0; --S) {
                    int sum = 0;
                    for(int j = 0; j < maxk; ++j)
                        if((S >> j) & 1) sum += s[i].val[j];
                    maxSum[S] = max(maxSum[S], sum);
                }
            }
            printf("%d\n", dfs((1 << maxk) - 1, k));
        }
    }
    return 0;
}

UVa 10012 - How Big Is It? UVa 10795 - A Different Task