看起来像一道构造题？然而不需要输出方案。
有点像背包，但是同一个城堡要考虑所有玩家的贡献。
考虑转换模型，我们发现同一座城堡玩家的顺序并没有影响。
设 \(a_{i,j}\) 表示第 \(i\) 个城堡，升序后第 \(j\) 个玩家派遣的士兵数。
那么我们构造出 \(n\) 组物品，每一组中有 \(s\) 个，\(w_{i,j},v_{i,j}\) 分别表示第 \(i\) 组中第 \(j\) 个物品的花费和价值。
有 \(w_{i,j} = 2a_{i,j} + 1,v_{i,j} = i \cdot j\)。
因为同一组已经排了序，选了第 \(j\) 个，\(1,\dots,j - 1\) 个也会有贡献，所以一共贡献了 \(j\) 次，每次有 \(i\) 的价值。
\(O(snm)\) 一遍分组背包即可，常数很小，AC 无压力。
代码： 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
using namespace std;
const int S = 100;
const int N = 100;
const int M = 2e4;
int s,n,m;
int a[N + 5][S + 5];
int w[N + 5][S + 5],v[N + 5][S + 5];
int f[N + 5][M + 5];
int ans;
int main()
{
scanf("%d%d%d",&s,&n,&m);
for(register int i = 1;i <= s;++i)
for(register int j = 1;j <= n;++j)
scanf("%d",a[j] + i);
for(register int i = 1;i <= n;++i)
{
sort(a[i] + 1,a[i] + s + 1);
for(register int j = 1;j <= s;++j)
w[i][j] = 2 * a[i][j] + 1,v[i][j] = i * j;
for(register int j = 1;j <= m;++j)
{
f[i][j] = f[i - 1][j];
for(register int k = 1;k <= s;++k)
if(w[i][k] <= j)
f[i][j] = max(f[i][j],f[i - 1][j - w[i][k]] + v[i][k]);
}
}
for(register int i = 1;i <= m;++i)
ans = max(ans,f[n][i]);
printf("%d\n",ans);
}