洛谷 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] 即可。

代码:

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N = 20020;
  7. int f[N];
  8. int a[200][200];
  9. int n, m, s;
  10. int main()
  11. {
  12. cin >> s >> n >> m;
  13. for (int i = 1; i <= s; i ++)
  14. for (int j = 1; j <= n; j ++)
  15. cin >> a[j][i];
  16. for (int i = 1; i <= n; i ++)
  17. sort(a[i] + 1, a[i] + s + 1);
  18. for (int i = 1; i <= n; i ++)
  19. for (int j = m; j >= 0; j --)
  20. for (int k = 1; k <= s; k ++)
  21. {
  22. if (j > a[i][k] * 2)
  23. {
  24. f[j] = max(f[j - a[i][k] * 2 - 1] + i * k, f[j]);
  25. }
  26. }
  27. cout << f[m] << endl;
  28. return 0;
  29. }
添加新评论