洛谷P5322 [BJOI2019] 排兵布阵

题目大意

有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;
}