LibreOJ 3092 「BJOI2019」排兵布阵

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

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

那么我们构造出 n 组物品，每一组中有 s 个，wi,j,vi,j 分别表示第 i 组中第 j 个物品的花费和价值。
有 wi,j=2ai,j+1,vi,j=i⋅j。
因为同一组已经排了序，选了第 j 个，1,…,j−1 个也会有贡献，所以一共贡献了 j 次，每次有 i 的价值。

O(snm) 一遍分组背包即可，常数很小，AC 无压力。

代码：

#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);
}