单调队列优化DP

先存这里
理解了再继续编写

CF1077F2 Pictures with Kittens (hard version)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=5e3+10;
const ll inf=1e18;

ll read() {
	
	ll x=0,f=1;
	char ch=getchar();
	while(ch<48||ch>57) {
		if(ch=='-') f=-1;
		ch=getchar(); 
	}
	while(ch>=48&&ch<=57) {
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;
	
}

ll n,k,m;
ll a[N],ans=-1;
ll dp[N][N],q[N];

/*

dp[i][j]表示前i个数中选了j个，第i个必取，可得到的最大和 
dp[i][j]=max(dp[u][j-1]+a[i]); 

*/

int main() {
	
	n=read();
	k=read();
	m=read();
	
	for(ll i=0;i<=n;i++) {
		
		for(ll j=0;j<=m;j++) {
			
			dp[i][j]=-inf;
			
		}
		
	}
	
	for(ll i=1;i<=n;i++) {
		
		a[i]=read();
		
	}	
	
	dp[0][0]=0;
	for(ll j=1;j<=m;j++) {
		
		ll l=1,r=1;
		q[r]=0;
		for(ll i=1;i<=n;i++) {
			
			while(l<=r&&q[l]+k<i) l++;
			dp[i][j]=dp[q[l]][j-1]+a[i];
			while(l<=r&&dp[i][j-1]>=dp[q[r]][j-1]) r--;
			q[++r]=i;
			
		}
		
	}
	
	for(ll i=n-k+1;i<=n;i++) ans=max(ans,dp[i][m]);
	printf("%lld\n",ans);
	
	return 0;
}