洛谷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;
}