[洛谷 5322,loj 3092][BJOI2019]排兵布阵

题目链接

https://www.luogu.org/problem/P5322

https://loj.ac/problem/3092

题解

当 \(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;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据