自动搬运

查看原文

来自洛谷，原作者为

	WarningQAQ 私永遠に百鬼あやめが好きです

搬运于2025-08-24 22:18:47，当前版本为作者最后更新于2020-09-27 19:26:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析：

首先有一种想法是直接枚举每场比赛所有参赛者的最高得分，并计算方案数，然后拿这个方案数与给出的那个 $C$ 比较。但这样的可能是错的（求证明QAQ），因为方案数可能为 $0$，因而无法保证遍历到的状态不会超过 $C$ 种。

一件奇怪的事情是考虑对于任何一种 $k$ 个参赛选手的集合，求一个这 $k$ 个选手的排序。可以采用的一种策略是：把第一场比赛得分最高的排在第一位，剩下的人中第二场比赛得分最高的排在第二位，以此类推。

考虑怎么求最优解。一种可行的策略是，先选第一场比赛得分最高的，再在剩下的人中选第二场比赛得分最高的，以此类推。显然这个贪心选取的顺序是符合上述排序的。

求出最优解后，不难把剩下的所有方案根据与当前方案的 $lcp$ 划分成 $k$ 类，每一类都相当于固定了方案的一个前缀，且要求这个前缀的下一位不能是某个选手。 而根据前面讲的那个排序，会发现一个长度为 $j$ 的前缀一定会确定前 $j$ 场比赛的最高得分，也就是说限制一个固定前缀的下一位不能填原本的最大值等价于限制了这个原本的最大值再也不能出现。 因此就可以用一个 bitset 维护尚可以出现在方案中的选手。

So，搜索的状态需要记录以下信息：一个被固定的前缀，尚可以选的集合，以及权值。 状态的权值应被定义为这个状态能给出的权值最大的方案的权值，计算出这个权值可以使用上述的贪心，紧接着便可以再根据剩余与当前方案的 $lcp$ 划分成不超过 $k$ 个子状态。

时间复杂度大概是 $O(nk2C)$ 。

代码：

#include "cstdio"
#include "algorithm"
#include "queue"
#include "bitset"
#include "cstring"
using namespace std;
struct node {
    bitset<505> S;
    vector<int> V;
    int pos, val;
    bool operator<(const node& b) const { return val < b.val; }
} O;
int n, k, c, a[505][10];
priority_queue<node> Q;
inline void fix(node x) {
    static int tmp[10];
    for (int i = 1; i <= k; ++i) tmp[i] = 0;
    x.pos = x.V.size();
    for (int i = 1; i <= x.pos; ++i)
        for (int j = 1; j <= k; ++j) tmp[j] = max(tmp[j], a[x.V[i - 1]][j]);
    for (int i = x.pos + 1; i <= k; ++i) {
        int id = -1;
        for (int j = 1; j <= n; ++j)
            if (x.S[j] && (id == -1 || a[j][i] >= a[id][i]))
                id = j;
        if (id == -1)
            return;
        for (int j = 1; j <= k; ++j) tmp[j] = max(tmp[j], a[id][j]);
        x.V.push_back(id);
        x.S[id] = 0;
    }
    x.val = 0;
    for (int i = 1; i <= k; ++i) x.val += tmp[i];
    Q.push(x);
}
int main() {
    scanf("%d%d%d", &n, &k, &c);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= k; ++j) scanf("%d", &a[i][j]);
    O.S.set();
    fix(O);
    while (c--) {
        node x = Q.top();
        Q.pop();
        if (!c)
            return printf("%d", x.val), 0;
        for (int i = x.pos; i < k; ++i) {
            node y = x;
            y.V.resize(i);
            y.S[x.V[i]] = 0;
            for (int j = i + 1; j < k; ++j) y.S[x.V[j]] = 1;
            fix(y);
        }
    }
    return 0;
}