目录
显示
题目链接
https://www.luogu.org/problem/P5322
题解
当 \(s=1\) 时，本题显然是一个经典的 0/1 背包问题。
现在让我们考虑 \(s>1\) 的情况。
如果一个人在一座城堡上派驻了 \(x\)，我们只需派驻 \(2x+1\) 人即可占领这座城堡。而对于那些派驻人数不到 \(x\) 人的对手，我们显然也能用 \(2x+1\) 占领城堡。
于是我们注意到了这个问题中的一个单调性：我们将每座城堡中各个玩家的用兵数排序，对于第 \(i\) 个城堡，假如我们能战胜第 \(k\) 个敌人，即意味着我们在这个城堡可以战胜前 \(k\) 个敌人，拿到 \(i \times k\) 的分数。
容易发现这是一个分组背包的模型，转移方程并不难写出。
设 \(f[j]\) 代表兵力为 \(j\) 时的最大收益，\(a[i][k]\) 代表 \(i\) 号城堡第 \(k\) 个人的派兵数（已经排序），我们转移时枚举城堡编号 \(i\)，派驻兵力数 \(j\) 和对手 \(k\)。
则有如下转移方程：
$$f[j]=\max(f[j],f[j-(2 \times a[i][k]+1)]+i \times k)$$
时间复杂度为 \(O(nmk)\)。
#include <cstdio>
#include <algorithm>
using namespace std;
int a[105][105],f[20005];
int main()
{
int s,n,m;
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 i=1;i<=n;i++)
for(int j=m;j>=0;j--)
for(int k=1;k<=s;k++)
if(j>=2*a[i][k]+1)f[j]=max(f[j],f[j-(2*a[i][k]+1)]+i*k);
printf("%d\n",f[m]);
return 0;
}