[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\%) 的数据： (nle 10,mle 100)
对于另外 (20\%) 的数据： (s=1)
对于 (100\%) 的数据： (1le s le 100) (1le n le 100) (1le m le 20000) 对于每名玩家 (a_i ge 0)，(sumlimits_{i=1}^n a_i le m)
算法解析
题意理解
你有(m)个士兵，可以把它们随意分配到(i)个城堡里，对于你的每一个敌人,在(i)这个城堡.
每次每个城堡派遣士兵的策略要求一致，现在知道其余玩家的派兵情况，求总得分最大值
算法解析
这道题目是省选的签到题目,非常友好.
首先,我们发现这道题目是,特别的背包问题.
对于第(x)个对手,然后针对(i)这个城堡,如果我们要占领它,那么花费最少多少?
这个就是我们对于这一个对手,这一个城堡的花费代价.
因此,我们构造出来了这个属于这个对手,这个城堡的物品.
然后我们设置一下状态表示.
既然如此,我们不妨对于一个城堡而言,将所有对手放置兵力将其排序.则
愉快的解决了.
代码解析
#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
",ans);
return 0;
}