题意
一个游戏，有 $n$ 座城堡，每局对战有两名玩家，每名玩家有 $m$ 个士兵，每人可以向第 $i$ 个城堡派遣 $a_i$ 名士兵，士兵总数满足：$a_1+a_2+\cdots+a_n\leq m$.
二人争夺这些城堡，如果一名玩家向城堡 $i$ 派遣的士兵数严格大于对手士兵数的两倍，那么这名玩家占领了这座城堡，获得 $i$ 分。
现给定 $s$ 名玩家及其各自的派兵策略，你需要选定一个固定的派兵策略，最大化你在 $s$ 场游戏中的总得分。
$1\leq s\leq 100, 1\leq n\leq 100, 1\leq m\leq 20000$.
分析
考虑DP。
设 $f_{i,j}$ 表示：对于前 $i$ 个城堡共派出 $j$ 个士兵；设 $a_{i,j}$ 表示：在城堡 $i$，玩家 $j$ 的出兵数量。
对每个城堡，把各个玩家在该城堡的出兵数量，按升序排序。
这样一来，若你在城堡 $i$ 的出兵数量大于 $2\times a_{i,j}$，则你可以在城堡 $i$ 获得 $i\times j$ 的得分。
于是对每个赢得城堡 $i$，枚举要战胜前 $k$ 个玩家，分别转移即可：
$$
f[i][j]=\max_{k=1}^s
\left\{
\begin{array}{lr}
0, &j-a_{i,k}\times 2 – 1 < 0\\
f[i][j-a_{i, k}\times2-1]+k\cdot i, &j-a_{i,k}\times2-1\geq 0
\end{array}
\right.
$$
f[i][j]=\max_{k=1}^s
\left\{
\begin{array}{lr}
0, &j-a_{i,k}\times 2 – 1 < 0\\
f[i][j-a_{i, k}\times2-1]+k\cdot i, &j-a_{i,k}\times2-1\geq 0
\end{array}
\right.
$$
属于分组背包模型。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 108, MAXM = 20008, MAXS = 108;
int s, n, m;
int dp[MAXM], a[MAXN][MAXS];//a[i][j]表示第i个城堡，第j个玩家
int main() {
scanf("%d%d%d", &s, &n, &m);
for(int i = 1; i <= s; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &a[j][i]);
for(int i = 1; i <= n; i++)
sort(a[i] + 1, a[i] + s + 1);
for(int k = 1; k <= n; k++) {
for(int i = m; i > 0; i--) {
for(int j = 1; j <= s; j++) {
if(i >= a[k][j] * 2 + 1) {
dp[i] = max(dp[i], dp[i - a[k][j] * 2 - 1] + k * j);
}
}
}
}
cout << dp[m] << endl;
return 0;
}