【SPOJ283】Naptime

题目大意：给定一个由 N 个点组成的环，点有点权，现从中选出 M 个点，对于顺时针方向来说，每一段被选取的第一个点的点权不计入答案贡献，求选出的最大权值是多少。

题解：首先考虑线性的情况，设 \(dp[i][j][0/1]\) 表示前 i 个点选择了 j 个点，且第 i 个点是否被选择的最优解。既然是线性，则第一个点被选取的话，一定不计入答案贡献，因此初始化为：\(dp[1][1][1]=dp[1][0][0]=0\)。再把环对答案的贡献考虑进去，发现只有第 1 个点被选中，且权值计入答案中这种情况被忽略掉了，因此，只需初始化\(dp[1][1][1]=w[1]\)，且最后统计答案时，取 dp[n][m][1] 参与答案贡献的计算即可。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=4000;

int n,m,w[maxn],dp[maxn][maxn][2],ans;

void read_and_parse(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)scanf("%d",&w[i]);

}

void solve(){

	memset(dp,0xcf,sizeof(dp));

	dp[1][0][0]=dp[1][1][1]=0;

	for(int i=2;i<=n;i++)

		for(int j=0;j<=min(i,m);j++){

			dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);

			if(j>=1)dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+w[i]);

		}

	ans=max(dp[n][m][0],dp[n][m][1]);

	memset(dp,0xcf,sizeof(dp));

	dp[1][1][1]=w[1];

	for(int i=2;i<=n;i++)

		for(int j=0;j<=min(i,m);j++){

			dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);

			if(j>=1)dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+w[i]);

		}

	ans=max(ans,dp[n][m][1]);

	printf("%d\n",ans);

}

int main(){

	int T;scanf("%d",&T);

	while(T--){

		read_and_parse();

		solve();

	}

	return 0;

}

巴特西

【SPOJ283】Naptime

最新文章

热门文章