T2-18 排兵布阵

题意理解

有 $n$ 座城堡，小 C 要和 $s$ 个对手对战（方案必须相同）。占领第 $i$ 座城堡需要派遣严格大于对手两倍的士兵，得 $i$ 分。总士兵数不超过 $m$，求最大总得分。

---

思路分析

这是一个分组背包问题。

对于每座城堡 $i$，小 C 有 $s+1$ 种选择：击败 $0, 1, 2, \\cdots, s$ 个对手。

预处理： 对于每座城堡，将 $s$ 个对手的派兵数排序。要击败派兵最少的 $k$ 个对手，需要的士兵数是 $2 \times sorted[k] + 1$，得分是 $k \times i$。

分组背包： 每座城堡是一组，每组选一个方案（击败多少对手），求总得分最大。

设 $dp[j]$ 表示：用 $j$ 个士兵能获得的最大得分。

边界条件：

• $dp[0] = 0$

答案： $dp[m]$

---

参考代码

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

const int MAXS = 105;   // 最大对手数
const int MAXN = 105;   // 最大城堡数
const int MAXM = 20005; // 最大士兵数

int s, n, m;            // 对手数、城堡数、士兵数
int a[MAXS][MAXN];      // a[j][i]表示第j个对手在第i座城堡的派兵数
int b[MAXN][MAXS];      // b[i][k]表示第i座城堡击败k个对手需要的士兵数
int dp[MAXM];           // dp[j]表示用j个士兵能获得的最大得分

int main() {
    cin >> s >> n >> m;  // 读入对手数、城堡数、士兵数
    
    for (int j = 1; j <= s; j++) {  // 读入每个对手的策略
        for (int i = 1; i <= n; i++) {
            cin >> a[j][i];
        }
    }
    
    // 预处理每座城堡击败k个对手需要的士兵数
    for (int i = 1; i <= n; i++) {  // 枚举每座城堡
        int tmp[MAXS];
        for (int j = 1; j <= s; j++) {  // 收集所有对手在该城堡的派兵数
            tmp[j] = a[j][i];
        }
        sort(tmp + 1, tmp + s + 1);  // 从小到大排序
        
        b[i][0] = 0;  // 击败0个对手不需要士兵
        for (int k = 1; k <= s; k++) {  // 击败前k个对手（派兵最少的k个）
            b[i][k] = 2 * tmp[k] + 1;  // 需要严格大于两倍
        }
    }
    
    // 分组背包
    dp[0] = 0;  // 边界
    
    for (int i = 1; i <= n; i++) {  // 枚举每座城堡（每组）
        for (int j = m; j >= 0; j--) {  // 逆序枚举士兵数
            for (int k = 1; k <= s; k++) {  // 枚举击败k个对手
                if (j >= b[i][k]) {  // 士兵数足够
                    dp[j] = max(dp[j], dp[j - b[i][k]] + k * i);  // 得分为k*i
                }
            }
        }
    }
    
    cout << dp[m] << endl;  // 输出答案
    return 0;
}