更好的阅读体验

[BJOI2019]排兵布阵

题目描述

小C正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵，可以向第$i$座城堡派遣 $a_i$ 名士兵去争夺这个城堡，使得总士兵数不超过 $m$。 如果一名玩家向第 $i$ 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 $i$ 分。 现在小C即将和其他 $s$ 名玩家两两对战，这 $s$ 场对决的派遣士兵方案必须相同。小C通过某些途径得知了其他 $s$ 名玩家即将使用的策略，他想知道他应该使用什么策略来最大化自己的总分。 由于答案可能不唯一，你只需要输出小C总分的最大值。

输入输出格式

输入格式

输入第一行包含三个正整数 $s,n,m$，分别表示除了小C以外的玩家人数、城堡数和每名玩家拥有的士兵数。 接下来 $s$ 行，每行 $n$ 个非负整数，表示一名玩家的策略，其中第 $i$ 个数 $a_i$ 表示这名玩家向第 $i$ 座城堡派遣的士兵数。

输出格式

输出一行一个非负整数，表示小C获得的最大得分。

输入输出样例

输入样例 #1

1 3 10
2 2 6

输出样例 #1

3

输入样例 #2

2 3 10
2 2 6
0 0 0

输出样例 #2

8

样例1解释： 小C的最佳策略为向第 $1$ 座城堡和第 $2$ 座城堡各派遣 $5$ 名士兵。

样例2解释： 小C的最佳策略之一为向第 $1$ 座城堡派遣 $2$ 名士兵，向第 $2$ 座城堡派遣 $5$ 名士兵，向第 $3$ 座城堡派遣 $1$ 名士兵。

数据范围

对于 $10\%$ 的数据： $s=1,n \le 3,m \le 10$

对于$20\%$ 的数据： $s=1,n \le 10,m \le 100$

对于 $40\%$ 的数据： $n\le 10,m\le 100$

对于另外 $20\%$ 的数据： $s=1$

对于 $100\%$ 的数据： $1\le s \le 100$ $1\le n \le 100$ $1\le m \le 20000$ 对于每名玩家 $a_i \ge 0$，$\sum\limits_{i=1}^n a_i \le m$

算法解析

题意理解

你有$m$个士兵，可以把它们随意分配到$i$个城堡里，对于你的每一个敌人,在$i$这个城堡.
$$ 你派兵的数量>2 \times 对手派兵的数量 \\\\则你的得分+=i $$
每次每个城堡派遣士兵的策略要求一致，现在知道其余玩家的派兵情况，求总得分最大值

算法解析

这道题目是省选的签到题目,非常友好.

首先,我们发现这道题目是,特别的背包问题.

对于第$x$个对手,然后针对$i$这个城堡,如果我们要占领它,那么花费最少多少?
$$ a[x][i]= 对手x在i放置的兵力\times 2+1 \\\\ $$
这个就是我们对于这一个对手,这一个城堡的花费代价.

因此,我们构造出来了这个属于这个对手,这个城堡的物品.

然后我们设置一下状态表示.
$$ f[i][j]第i个城堡,派出了j个士兵的最大利润 $$
既然如此,我们不妨对于一个城堡而言,将所有对手放置兵力将其排序.则
$$ f[i][j]=max(f[i][j],f[j-a[i][k]]+i \times k) \\\\k表示第k个对手.因为已经排序,所以前k个对手都可以战胜 $$
愉快的解决了.
$$ 复杂度为O(s \times n \times m) $$

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+20;
int s,n,m,dp[N],a[110][110],ans;
signed main()
{
    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]);
            a[j][i]=a[j][i]*2+1;//这里是第j个城堡,第i个对手,这样是为了便于排序
        }
    for(int i=1; i<=n; i++)
        sort(a[i]+1,a[i]+1+s);//排序
    for(int i=1; i<=n; i++)//第i个城堡
        for(int j=m; j>=0; j--)//背包容量
            for(int k=1; k<=s; k++) //第k个对手
                if(j>=a[i][k])//可以放置
                    dp[j]=max(dp[j-a[i][k]]+k*i,dp[j]);
    for(int i=0; i<=m; i++)
        ans=max(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}