[BJOI2019] 排兵布阵

题意

有 s 个对手、n 座城堡，小 C 有 m 名士兵。

每个对手都已经确定了一套派兵方案，第 j 座城堡会派出若干士兵。

小 C 也要给每座城堡派兵，但总兵力不能超过 m。

如果小 C 在某座城堡派出的士兵数严格大于某个对手在这座城堡派出的士兵数的两倍，那么小 C 就能占领这座城堡，得到这座城堡的编号分数。

小 C 要面对所有 s 个对手，而且自己的派兵方案必须对所有对手都一样，求总得分最大值。

这张表把题意翻成了背包模型：

原题对象	背包含义
一座城堡	一个分组
在该城堡派多少兵	组内的选择
占领后得到的分数	组内价值
总兵力 `m`	背包容量

思路

先看一个可以直接验证正确性的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52#include <bits/stdc++.h>
using namespace std;

static int s, n, m;
static vector<vector<int>> enemy;
static vector<int> choice;
static int best = 0;

static int score_for_castle(int castle, int x) {
    int cnt = 0;
    for (int i = 1; i <= s; ++i) {
        if (x > 2 * enemy[i][castle]) {
            ++cnt;
        }
    }
    return cnt * castle;
}

static void dfs(int castle, int used, int sum_score) {
    if (castle > n) {
        best = max(best, sum_score);
        return;
    }

    // 不给这座城堡派兵。
    dfs(castle + 1, used, sum_score);

    // 枚举给这座城堡派多少兵。
    for (int x = 1; x + used <= m; ++x) {
        choice[castle] = x;
        dfs(castle + 1, used + x, sum_score + score_for_castle(castle, x));
        choice[castle] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s >> n >> m;
    enemy.assign(s + 1, vector<int>(n + 1));
    for (int i = 1; i <= s; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> enemy[i][j];
        }
    }

    choice.assign(n + 1, 0);
    dfs(1, 0, 0);
    cout << best << '\n';
    return 0;
}

brute.cpp 直接枚举每座城堡派多少兵，再计算最终得分，适合小数据对拍。

关键观察是：对某一座城堡来说，小 C 派 x 个兵时，能打赢的对手一定是“这座城堡上派兵数小于 x/2 的那些人”。

所以把所有对手在这座城堡上的派兵数从小到大排序后，再合并相同值，就会形成一串“台阶”：

打赢前 `k` 个对手	最小派兵数	得分
`k = 0`	`0`	`0`
打赢所有兵力为 `v1` 的对手	`2 * v1 + 1`	`cnt(v1) * i`
打赢所有兵力为 `v2` 的对手	`2 * v2 + 1`	`cnt(v2) * i`
打赢所有兵力为 `v3` 的对手	`2 * v3 + 1`	`cnt(v3) * i`

其中 cnt(v) 表示所有派兵数不超过 v 的对手总数。

这说明每座城堡都能转成至多 s 个可选方案：

花 2 * v + 1 个兵
得到 cnt(v) * i 分

于是问题就变成了标准的分组背包：

每座城堡是一组
组内可以选 0 个或 1 个方案
所有组加起来的总兵力不超过 m

对每座城堡，先把 s 个敌方派兵数排序，然后枚举这些阈值方案即可。

DP 公式

对第 $i$ 座城堡，把每个可选台阶记为 $(cost_{i,p}, value_{i,p})$ 。设 $dp_j$ 表示已经处理若干座城堡、总兵力不超过 $j$ 时的最大得分。分组背包转移为：

new_j=\max\left(dp_j,\ \max_{p,\ cost_{i,p}\leqslant j}\{dp_{j-cost_{i,p}}+value_{i,p}\}\right)

每座城堡最多选择一个台阶方案。最终答案为：

dp_m

公式解释：一座城堡的派兵数只在超过某些敌方阈值时改变得分，所以可以离散成若干台阶方案。每座城堡最多选一个台阶，多个城堡之间共享总兵力容量，因此是分组背包。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int s, n, m;
    cin >> s >> n >> m;

    vector<vector<int>> a(n + 1, vector<int>(s + 1));
    for (int i = 1; i <= s; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> a[j][i];
        }
    }

    for (int i = 1; i <= n; ++i) {
        sort(a[i].begin() + 1, a[i].end());
    }

    vector<int> dp(m + 1, 0);

    for (int castle = 1; castle <= n; ++castle) {
        vector<pair<int, int>> options;
        int beaten = 0;
        for (int k = 1; k <= s; ) {
            int v = a[castle][k];
            while (k <= s && a[castle][k] == v) {
                ++k;
                ++beaten;
            }
            int cost = 2 * v + 1;
            if (cost <= m) {
                options.push_back({cost, castle * beaten});
            }
        }

        vector<int> ndp = dp;
        for (auto [cost, value] : options) {
            for (int money = cost; money <= m; ++money) {
                ndp[money] = max(ndp[money], dp[money - cost] + value);
            }
        }
        dp.swap(ndp);
    }

    cout << dp[m] << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n * s * m)$
空间复杂度： $O(m)$

这里 n <= 100，s <= 100，m <= 2e4，这个复杂度可以接受。

总结

这题的本质不是“模拟战斗”，而是“把每座城堡的得分曲线离散成若干台阶”。

一旦把台阶列出来，每座城堡就成了一个分组，后面就是标准分组背包。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。