CF1077F2 Solution

题目链接

题解

仅在easy version上增加单调队列优化即可，简单版题解。但注意为使单调队列中数据为之前卡牌，需要倒序转移（与01背包滚动数组相似）。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5001,inf=0x3f3f3f3f3f3f3f3f;
int a[N],dp[N][N],tl[N],hd[N],q[N][N];
//q[i][]:当前dp[][i](已选出i张)的单调队列,hd/tl[i]:q[i][]的队首/队尾
signed main()
{
	int k,x,n,ans=-inf;
	scanf("%lld%lld%lld",&n,&k,&x);
	memset(dp,-0x3f,sizeof(dp));
	for(int i=1;i<=n;i++) {scanf("%lld",&a[i]); dp[i][0]=0;}
	for(int i=1;i<=n;i++)
	{
		for(int j=min(i,x);j>=2;j--)
		{
            //需先删头后去尾(与模板不同)
			while(q[j-1][hd[j-1]]<i-k && hd[j-1]<=tl[j-1]) hd[j-1]++;
			if(hd[j-1]<=tl[j-1]) dp[i][j]=dp[q[j-1][hd[j-1]]][j-1]+a[i];
			while(dp[q[j][tl[j]]][j]<dp[i][j] && hd[j]<=tl[j]) tl[j]--;
			q[j][++tl[j]]=i;
		}
		if(i<=k) 
		{
			dp[i][1]=a[i];
			while(dp[q[1][tl[1]]][1]<dp[i][1] && hd[1]<=tl[1]) tl[1]--;
			q[1][++tl[1]]=i;
			while(q[1][hd[1]]<i-k && hd[1]<=tl[1]) hd[1]++;
		} 
	}
	for(int i=n-k+1;i<=n;i++) ans=max(ans,dp[i][x]);
	if(ans<0) printf("-1");
	else printf("%lld",ans);
	return 0;
}