洛谷P5322 [BJOI2019] 排兵布阵 题解

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[20001],a[101][101],s,n,m;
signed main(){
	cin>>s>>n>>m;
	for(int j=1;j<=s;j++){
		for(int i=1;i<=n;i++){
			cin>>a[i][j];
		}
	}
	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>2*a[i][k])dp[j]=max(dp[j],dp[j-2*a[i][k]-1]+k*i);
			}
		}
	}
	cout<<dp[m]<<endl;
	return 0;
}

题解

我们用滚动 dp 来完成这道题，其中  表示在前  个城堡放  个士兵的最高分。

第  行对各个对手的士兵数升序排列，这样方便计算转移时的贡献。

由于滚动数组是倒着滚的，所以  行要从大到小排。

第  行解释：如果剩下的士兵可以抢下这个城堡，那么我们取选与不选总分的最大值。

最后输出在有  个士兵的情况下的最高分，即 。