【洛谷-P5322】[BJOI2019]排兵布阵 • TonyYin's Blog

题意#

一个游戏，有 $n$ 座城堡，每局对战有两名玩家，每名玩家有 $m$ 个士兵，每人可以向第 $i$ 个城堡派遣 $a_i$ 名士兵，士兵总数满足： $a_1+a_2+\cdots+a_n\leq m$ .

二人争夺这些城堡，如果一名玩家向城堡 $i$ 派遣的士兵数严格大于对手士兵数的两倍，那么这名玩家占领了这座城堡，获得 $i$ 分。

现给定 $s$ 名玩家及其各自的派兵策略，你需要选定一个固定的派兵策略，最大化你在 $s$ 场游戏中的总得分。

$1\leq s\leq 100, 1\leq n\leq 100, 1\leq m\leq 20000$ .

分析#

考虑DP。

设 $f_{i,j}$ 表示：对于前 $i$ 个城堡共派出 $j$ 个士兵；设 $a_{i,j}$ 表示：在城堡 $i$ ，玩家 $j$ 的出兵数量。

对每个城堡，把各个玩家在该城堡的出兵数量，按升序排序。

这样一来，若你在城堡 $i$ 的出兵数量大于 $2\times a_{i,j}$ ，则你可以在城堡 $i$ 获得 $i\times j$ 的得分。

于是对每个赢得城堡 $i$ ，枚举要战胜前 $k$ 个玩家，分别转移即可：

f[i][j]=\max_{k=1}^s \left\{ \begin{array}{lr} 0, &j-a_{i,k}\times 2 - 1 < 0\\ f[i][j-a_{i, k}\times2-1]+k\cdot i, &j-a_{i,k}\times2-1\geq 0 \end{array} \right.

属于分组背包模型。

代码#

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 108, MAXM = 20008, MAXS = 108;
int s, n, m;
int dp[MAXM], a[MAXN][MAXS];//a[i][j]表示第i个城堡，第j个玩家
int main() {
	scanf("%d%d%d", &s, &n, &m);
	for(int i = 1; i <= s; i++)
		for(int j = 1; j <= n; j++)
			scanf("%d", &a[j][i]);
	for(int i = 1; i <= n; i++)
		sort(a[i] + 1, a[i] + s + 1);
	for(int k = 1; k <= n; k++) {
		for(int i = m; i > 0; i--) {
			for(int j = 1; j <= s; j++) {
				if(i >= a[k][j] * 2 + 1) {
					dp[i] = max(dp[i], dp[i - a[k][j] * 2 - 1] + k * j);
				}
			}
		}
	}
	cout << dp[m] << endl;
	return 0;
}

cpp