P5322 BJOI2019 排兵布阵

P5322 BJOI2019 排兵布阵

本题主要考察对模型的转化能力。

首先要察觉两条性质：

• 对于一个城堡，想打败一个玩家的同时用最少的士兵，肯定是正好派出这个玩家在这个城堡派出的士兵数量的二倍加一名士兵。
• 在一个城堡上，打败了一个在这个城堡派出士兵数量为 \(x\) 的玩家，就可以顺便打败所有在这个城堡派出士兵数量 \(\le x\) 的玩家。

这两条性质可以推出一条关键结论：在总共 \(s\) 场对决中，如果想要占有第 \(i\) 个城堡恰好 \(k\) 次，拿到 \(k \times i\) 的积分，就必须打败 \(k\) 个玩家，为此我们应该找到在第 \(i\) 个城堡上，\(s\) 名玩家分别派出的士兵数量里的第 \(k\) 小的那个士兵数量（不妨设为 \(f(i, k)\)），并在这个城堡上拿出 \(f(i, k)\) 的二倍加一。

问题可以转化成：

总共 \(n\) 组物品（第 \(i\) 组物品对应第 \(i\) 个城堡），每组物品中有 \(s\) 个物品。

第 \(i\) 组中的第 \(k\) 个物品，体积为 \(2 \times f(i, k) + 1\)，价值为 \(i \times k\)。

这样以来，我们可以将在第 \(i\) 个城堡打败 \(k\) 个玩家的决策转化为选择第 \(i\) 组的第 \(k\) 个物品。

每组物品只能选择一个，因为选择第 \(i\) 组的第 \(k\) 个物品代表在第 \(i\) 个城堡打败 \(k\) 个玩家，而选择多个物品是没有意义的。

到这里就变成分组背包问题了。时间复杂度 \(\Theta(ns(m + \log s))\)。\(\log s\) 是因为需要排序预处理出 \(f(i, k)\)。

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2023-04-20 11:39:30 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2023-04-20 12:35:49
 */
#include <bits/stdc++.h>
inline int read() {
    int x = 0;
    bool f = true;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            f = false;
    for (; isdigit(ch); ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f ? x : (~(x - 1));
}
inline bool gmx(int &a, int b) {
    return b > a ? a = b, true : false;
}

const int maxs = 105;
const int maxn = 105;
const int maxm = 20005;

int f[maxm];
std :: vector <int> a[maxn];

int main() {
    int s = read(), n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i].push_back(0);
    
    for (int i = 1; i <= s; ++i)
        for (int j = 1; j <= n; ++j)
            a[j].push_back(read());

    for (int i = 1; i <= n; ++i)
        std :: sort(a[i].begin(), a[i].end());
    
    for (int i = 1; i <= n; ++i)
        for (int v = m; ~v; --v)
            for (int k = 1; k <= s && 2 * a[i][k] + 1 <= v; ++k)
                gmx(f[v], f[v - 2 * a[i][k] - 1] + i * k);
    
    printf("%d\n", f[m]);
    return 0;
}