BZOJ 5526.「BJOI2019」排兵布阵

看起来像一道构造题?然而不需要输出方案。
有点像背包,但是同一个城堡要考虑所有玩家的贡献。

考虑转换模型,我们发现同一座城堡玩家的顺序并没有影响。
ai,ja_{i,j} 表示第 ii 个城堡,升序后jj 个玩家派遣的士兵数。

那么我们构造出 nn 组物品,每一组中有 ss 个,wi,j,vi,jw_{i,j},v_{i,j} 分别表示第 ii 组中第 jj 个物品的花费和价值。
wi,j=2ai,j+1,vi,j=ijw_{i,j} = 2a_{i,j} + 1,v_{i,j} = i \cdot j
因为同一组已经排了序,选了第 jj 个, 个也会有贡献,所以一共贡献了 jj 次,每次有 ii 的价值。

O(snm)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
#include <cstdio>
#include <algorithm>
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);
}