洛谷 P5322 [BJOI2019] 排兵布阵

// ✗ P5322 的第一版：贪心 —— 「分越高的城堡越值得抢」。
//
// 城堡 i 值 i 分，所以从编号最大的城堡开始，一座一座地「能全赢就全赢」：
// 需要 `2·max(b) + 1` 个兵，掏得起就掏，掏不起就跳过。
//
// ⚠ 它一次错两处：
//   ① 不一定要**全赢** —— 只赢一部分对手往往便宜得多、也划算得多；
//   ② 高分城堡不一定划算 —— 分数是线性的（`i`），而费用可以差好几十倍。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int s, n, m;
    if (scanf("%d %d %d", &s, &n, &m) != 3) return 0;
    vector<vector<int>> b(n + 1, vector<int>(s));
    for (int j = 0; j < s; j++)
        for (int i = 1; i <= n; i++)
            if (scanf("%d", &b[i][j]) != 1) return 0;

    int left = m, sum = 0;
    for (int i = n; i >= 1; i--) {                     // 从分最高的城堡开始
        int need = 0;
        for (int j = 0; j < s; j++) need = max(need, 2 * b[i][j] + 1);
        if (need <= left) { left -= need; sum += s * i; }
    }
    printf("%d\n", sum);
    return 0;
}

// P5322 [BJOI2019] 排兵布阵 —— ★ 这一版就能 AC。
//
// ★★ 关键的一步（一）：**每座城堡只有 s + 1 种「有意义的派兵数」。**
//   把 s 个对手在第 i 座城堡的兵力排好序（b₁ ≤ b₂ ≤ … ≤ b_s），
//   想赢下前 k 个对手，最省的派法就是 `2·b_k + 1`（题面写的是**严格**大于两倍）。
//   派别的数目要么白花兵，要么多赢不了人。
//
// ★★ 关键的一步（二）：于是**每座城堡就是一组**，组内 s 件互斥物品：
//       第 k 件：费用 `2·b_k + 1`，价值 `k × i`（赢 k 个对手，每个给 i 分）
//   然后就是第 25 章下半场那三层循环：组 → 容量倒序 → 组内枚举。
//
// 复杂度 `O(nsm)`：顶格 100 × 100 × 2×10⁴ = 2 × 10⁸ —— 这道题就是卡着这个量级过的。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int s, n, m;
    if (scanf("%d %d %d", &s, &n, &m) != 3) return 0;
    vector<vector<int>> b(n + 1, vector<int>(s));      // b[城堡][对手]
    for (int j = 0; j < s; j++)
        for (int i = 1; i <= n; i++)
            if (scanf("%d", &b[i][j]) != 1) return 0;

    vector<int> f(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        sort(b[i].begin(), b[i].end());                // ★ 排完序，「赢前 k 个」才有意义
        for (int j = m; j >= 0; j--)
            for (int k = 1; k <= s; k++) {             // 组内枚举，必须在最里层
                int cost = 2 * b[i][k - 1] + 1;        // ★ 严格大于两倍 ⇒ 要多一个兵
                if (cost > j) break;                   // 费用随 k 单调不减，超了就不用再看
                f[j] = max(f[j], f[j - cost] + k * i);
            }
    }
    printf("%d\n", f[m]);
    return 0;
}

// ✗ P5322 的第一个坑：把「**严格**大于两倍」读成了「大于等于两倍」。
//
// 题面那个「严格」两个字是加粗的：
// 「如果一名玩家向第 i 座城堡派遣的士兵数**严格**大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡」。
//
// 这一版把费用写成 `2·b_k`（而不是 `2·b_k + 1`），于是每座城堡都少花 1 个兵。
// ★ 它最刺眼的地方在 `b = 0`：对手一个兵都不派时，它认为**我也不用派**就赢了。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int s, n, m;
    if (scanf("%d %d %d", &s, &n, &m) != 3) return 0;
    vector<vector<int>> b(n + 1, vector<int>(s));
    for (int j = 0; j < s; j++)
        for (int i = 1; i <= n; i++)
            if (scanf("%d", &b[i][j]) != 1) return 0;

    vector<int> f(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        sort(b[i].begin(), b[i].end());
        for (int j = m; j >= 0; j--)
            for (int k = 1; k <= s; k++) {
                int cost = 2 * b[i][k - 1];            // ✗ 少了那个 + 1
                if (cost > j) break;
                f[j] = max(f[j], f[j - cost] + k * i);
            }
    }
    printf("%d\n", f[m]);
    return 0;
}

// ✗ P5322 的第二个坑：组内那 s 件物品**没排序**。
//
// 「派 `2·b_k + 1` 个兵能赢 k 个对手」这句话，只有在 b 已经**从小到大排好**时才成立
// —— 它说的是「赢下最弱的那 k 个」。
//
// 这一版照输入顺序直接拿 b[k-1] 当第 k 件物品的费用，
// 于是「费用」和「赢几个」对不上号：花了赢 3 个的钱，可能只赢得了 1 个。
// ⚠ 而它**不一定错**：输入本来就有序的时候，它和正解一模一样（页面上量了这一档）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int s, n, m;
    if (scanf("%d %d %d", &s, &n, &m) != 3) return 0;
    vector<vector<int>> b(n + 1, vector<int>(s));
    for (int j = 0; j < s; j++)
        for (int i = 1; i <= n; i++)
            if (scanf("%d", &b[i][j]) != 1) return 0;

    vector<int> f(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        // ✗ 这里少了一句 sort
        for (int j = m; j >= 0; j--)
            for (int k = 1; k <= s; k++) {
                int cost = 2 * b[i][k - 1] + 1;
                if (cost <= j) f[j] = max(f[j], f[j - cost] + k * i);
            }
    }
    printf("%d\n", f[m]);
    return 0;
}