[BJOI2019] 排兵布阵
题目描述
小 C 正在玩一款排兵布阵的游戏。在游戏中有 \(n\) 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 \(m\) 名士兵，可以向第 \(i\) 座城堡派遣 \(a_i\) 名士兵去争夺这个城堡，使得总士兵数不超过 \(m\)。
如果一名玩家向第 \(i\) 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 \(i\) 分。
现在小 C 即将和其他 \(s\) 名玩家两两对战，这 \(s\) 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 \(s\) 名玩家即将使用的策略，他想知道他应该使用什么策略来最大化自己的总分。
由于答案可能不唯一，你只需要输出小 C 总分的最大值。
输入格式
输入第一行包含三个正整数 \(s,n,m\)，分别表示除了小 C 以外的玩家人数、城堡数和每名玩家拥有的士兵数。
接下来 \(s\) 行，每行 \(n\) 个非负整数，表示一名玩家的策略，其中第 \(i\) 个数 \(a_i\) 表示这名玩家向第 \(i\) 座城堡派遣的士兵数。
输出格式
输出一行一个非负整数，表示小 C 获得的最大得分。
样例 #1
样例输入 #1
1 3 10
2 2 6
样例输出 #1
3
样例 #2
样例输入 #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 \le 3,m \le 10\)
对于 \(20\%\) 的数据： \(s=1,n \le 10,m \le 100\)
对于 \(40\%\) 的数据： \(n\le 10,m\le 100\)
对于另外 \(20\%\) 的数据： \(s=1\)
对于 \(100\%\) 的数据：
\(1\le s \le 100\)
\(1\le n \le 100\)
\(1\le m \le 20000\)
对于每名玩家 \(a_i \ge 0\)，\(\sum\limits_{i=1}^n a_i \le m\)
解法：
分组背包
读懂题后很容易发现本题是一个分组背包问题。\(s\)场对局，\(n\)座城堡，\(s\)场对局的派遣方案必须统一。也就是说对于每一座城堡，都有且仅有一种派遣方式，使得在\(s\)场对局中能够拿到最多分数。
因此我们可以按照城堡的数量进行分组，每一组\(s\)个方案，如果我们派出的士兵数目大于其中第\(i\)大的方案\(a_i\)，也就是说所有\(a_j < a_i\)的对局中我们都能拿到分，那么这一座城堡我们能够拿到的分数为\(i \times j\). 我们最多能够派出\(m\)个士兵。
经过上面的分析，我们其实已经可以抽象出分组背包的模型了：有\(n\)组物品，每一组物品有\(s\)个，每一组物品最多只能取一个。每一件物品的价值为\(i * j\)，其中\(i\)表示第\(i\)组物品，\(j\)表示其体积\(v\)在第\(i\)组中按升序排序后的位置。每一件物品的体积\(v=2 * a + 1\)，其中\(a\)的含义就是题目中的敌对玩家派遣士兵数量。现有一个容积为\(m\)的背包，求在不超过背包容积下能拿的最大价值。接下来就是默写分组背包问题。
注：本题与一般的不一样，最后需要遍历数组取最大值，不是单纯返回\(f[m]\)
#include<bits/stdc++.h>
const int N = 110, M = 20034;
int s, n, m;
int f[M];
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin >> s >> n >> m;
std::vector<std::vector<int>> ba(n + 1, std::vector<int>(1, 0));
for(int i = 1; i <= s; i ++ ){
for(int j = 1; j <= n; j ++ ){
int x;
std::cin >> x;
ba[j].push_back(2 * x + 1);
}
}
for(int i = 1; i <= n; i ++ ){
std::sort(ba[i].begin(), ba[i].end());
}
for(int i = 1; i <= n; i ++ ){
for(int j = m; j >= 0; j -- ){
for(int k = 1; k <= s; k ++ ){
if(j >= ba[i][k]){
f[j] = std::max(f[j], f[j - ba[i][k]] + i * k);
}
}
}
}
int ans = 0;
for(int i = 0; i <= m; i ++ )
ans = std::max(f[i], ans);
std::cout << ans;
return 0;
}