洛谷 P5322 BJOI2019 排兵布阵

url: https://www.luogu.com.cn/problem/P5322

tag:
动态规划，背包DP

思路：
读入的时候反着读，用 a[i][j] 来表示第i座城第j个人出的兵。然后对每座城中的s种出兵的方式排序，得到 a[i][j] 表示第i座城前j个出兵最多的人出的兵。然后用分组背包的方式，每一座城每种出兵数量，用那座城的每一个前k个玩家出兵数量来更新f。最后输出 f[m] 即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20020;
int f[N];
int a[200][200];
int n, m, s;
int main()
{
    cin >> s >> n >> m;
    for (int i = 1; i <= s; i ++)
        for (int j = 1; j <= n; j ++)
            cin >> a[j][i];
    for (int i = 1; i <= n; i ++)
        sort(a[i] + 1, a[i] + s + 1);
    for (int i = 1; i <= n; i ++)
        for (int j = m; j >= 0; j --)
            for (int k = 1; k <= s; k ++)
            {
                if (j > a[i][k] * 2)
                {
                    f[j] = max(f[j - a[i][k] * 2 - 1] + i * k, f[j]);
                }
            }
    cout << f[m] << endl;
    return 0;
}