洛谷P5322 [BJOI2019] 排兵布阵 题解
题意:小 C 正在玩一款排兵布阵的游戏。在游戏中有 \(n\) 座城堡,每局对战由两名玩家来争夺这些城堡。每名玩家有 \(m\) 名士兵,可以向第 \(i\) 座城堡派遣 \(a_i\) 名士兵去争夺这个城堡,使得总士兵数不超过 \(m\)。
如果一名玩家向第 \(i\) 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍,那么这名玩家就占领了这座城堡,获得 \(i\) 分。
现在小 C 即将和其他 \(s\) 名玩家两两对战,这 \(s\) 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 \(s\) 名玩家即将使用的策略,他想知道他应该使用什么策略来最大化自己的总分。
由于答案可能不唯一,你只需要输出小 C 总分的最大值。
设 \(dp[i][j]\) 表示第 \(i\) 个城堡放 \(j\) 个士兵可以获得的最大分数
显然我们会选择恰好为某名玩家放的兵数 \(x\) 的 \(2x+1\) ,不然多的都是浪费
因此这就是个类似背包的问题
没什么难度,直接看代码就能明白了吧(逃
时间复杂度 \(O(nms)\)
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define S (int)(105)
#define N (int)(115)
#define M (int)(2e4+15)
int s,n,m;
int val[N][M],dp[M],b[N][S],mx[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> s >> n >> m;
for(int i=1; i<=s; i++)
for(int j=1; j<=n; j++)
cin >> b[j][i];
for(int i=1; i<=n; i++)
sort(b[i]+1,b[i]+1+s);
for(int i=1; i<=n; i++)
for(int j=m; j>=1; j--)
for(int k=1; k<=s; k++)
if(j>2*b[i][k]) dp[j]=max(dp[j],dp[j-2*b[i][k]-1]+k*i);
cout << dp[m] << endl;
return 0;
}