【CF1077F2】Pictures with Kittens 单调队列+dp

题目大意：给定一个长度为 N 的序列，点有点权，从序列中选出恰好 X 个数，并且保证任意连续的 K 个数中均有一个被选中，求选出的点权最大是多少。

题解：此题可以作为烽火传递+ 来处理，只不过在烽火传递的基础上加了选出恰好 X 个数，因此只需在状态维度上加上一维选出的个数即可，\(dp[i][j]\) 表示前 i 个数中选出 j 个数，且第 i 个数被选中的最优解，因此有状态转移方程：\(dp[i][j]=max\{dp[k][j-1],k\in[i-m,i-1] \}+val[i]\)，直接用单调队列进行优化即可。

同时，可以直接在初始化的时候将所有值设为无穷，避免了无效的状态转移，从而避免了不合法的解对答案的贡献，也就避免了讨论何时输出 -1 的问题。

代码如下

#include<bits/stdc++.h>

using namespace std;

const int maxn=5010;

int n,m,tot,val[maxn],q[maxn<<1],l,r;

long long dp[maxn][maxn],ans;

void read_and_parse(){

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

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

}

void solve(){

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

	dp[0][0]=0;

	for(int i=1;i<=tot;i++){

		l=1,r=0;

		for(int j=1;j<=n;j++){

			while(l<=r&&q[l]<j-m)++l;

			while(l<=r&&dp[j-1][i-1]>dp[q[r]][i-1])--r;

			q[++r]=j-1;

			dp[j][i]=dp[q[l]][i-1]+val[j];

		}

	}

	ans=-1;

	for(int i=n-m+1;i<=n;i++)ans=max(ans,dp[i][tot]);

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

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【CF1077F2】Pictures with Kittens 单调队列+dp

最新文章

热门文章