[BJOI2019]排兵布阵
题目描述
小C正在玩一款排兵布阵的游戏。在游戏中有 n 座城堡,每局对战由两名玩家来争夺这些城堡。每名玩家有 m 名士兵,可以向第i座城堡派遣 ai 名士兵去争夺这个城堡,使得总士兵数不超过 m。 如果一名玩家向第 i 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍,那么这名玩家就占领了这座城堡,获得 i 分。 现在小C即将和其他 s 名玩家两两对战,这 s 场对决的派遣士兵方案必须相同。小C通过某些途径得知了其他 s 名玩家即将使用的策略,他想知道他应该使用什么策略来最大化自己的总分。 由于答案可能不唯一,你只需要输出小C总分的最大值。
输入输出格式
输入格式
输入第一行包含三个正整数 s,n,m,分别表示除了小C以外的玩家人数、城堡数和每名玩家拥有的士兵数。 接下来 s 行,每行 n 个非负整数,表示一名玩家的策略,其中第 i 个数 ai 表示这名玩家向第 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≤3,m≤10
对于20% 的数据: s=1,n≤10,m≤100
对于 40% 的数据: n≤10,m≤100
对于另外 20% 的数据: s=1
对于 100% 的数据: 1≤s≤100 1≤n≤100 1≤m≤20000 对于每名玩家 ai≥0,n∑i=1ai≤m
算法解析
题意理解
你有m个士兵,可以把它们随意分配到i个城堡里,对于你的每一个敌人,在i这个城堡.
你派兵的数量>2×对手派兵的数量则你的得分+=i
每次每个城堡派遣士兵的策略要求一致,现在知道其余玩家的派兵情况,求总得分最大值
算法解析
这道题目是省选的签到题目,非常友好.
首先,我们发现这道题目是,特别的背包问题.
对于第x个对手,然后针对i这个城堡,如果我们要占领它,那么花费最少多少?
a[x][i]=对手x在i放置的兵力×2+1
这个就是我们对于这一个对手,这一个城堡的花费代价.
因此,我们构造出来了这个属于这个对手,这个城堡的物品.
然后我们设置一下状态表示.
f[i][j]第i个城堡,派出了j个士兵的最大利润
既然如此,我们不妨对于一个城堡而言,将所有对手放置兵力将其排序.则
f[i][j]=max(f[i][j],f[j−a[i][k]]+i×k)k表示第k个对手.因为已经排序,所以前k个对手都可以战胜
愉快的解决了.
复杂度为O(s×n×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;
}
太苣了
%%%sky大佬