洛谷P5322 [BJOI2019] 排兵布阵-JZTXT

题目大意

有s名对手，n座城堡，你有m名士兵

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

求最大得分

数据范围

对于 $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$

题解

不难想到用背包的方法去解决这道题

设第 $ i $ 座城堡派出兵力第 $ k$ 多的玩家派出了 $ a \left[ i \right] \left[ k \right]$名士兵

对于每座城堡的代价，一定是 $a \left[ i \right] \left[ k \right] \times 2 + 1$，因为题目中是严格大于，所以要 $+1$

如果派出兵力大于了 $a \left[ i \right] \left[ k \right] \times 2 + 1$，那多余的一定是浪费的

对于 $ a \left[ i \right] \left[ k \right] $，我们只需要在一开始将 $a$ 数组排序即可

$ d p $ 转移方程即为： $d p \left[ j \right] = \max \left( d p \left[ j - a\left[ i \right] \left[ k \right] \times 2 - 1 \right] + k \times i ,d p \left[ j \right] \right)$

#include<bits/stdc++.h>
using namespace std;
int s,n,m,dp[20010],ans,a[110][110];
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 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)
					dp[j] = max(dp[j],dp[j-a[i][k]*2-1]+i*k);
	for(int i = 0;i<=m;i++) ans = max(ans,dp[i]);
	printf("%d",ans);
	return 0;
}