P5858 「SWTR-03」Golden Sword(线性dp)

「SWTR-03」Golden Sword - 洛谷https://www.luogu.com.cn/problem/P5858

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN=1e6;
typedef long long ll;
const ll INF=0x3f3f3f3f*2;
ll a[MAXN];
int n,m,s;
ll dp[5005][5005];
int q[MAXN];
int head,tail;
int main(){memset(dp,-INF,sizeof(dp));scanf("%d %d %d",&n,&m,&s);for(int i=1;i<=n;i++){scanf("%lld",a+i);}dp[0][0]=0;for(int i=1;i<=n;i++){head=tail=1;q[head]=m;for(int j=m;j;j--){while(head<=tail&&q[head]>j+s-1){head++;}while(head<=tail&&dp[i-1][q[tail]]<dp[i-1][j-1]){tail--;}q[++tail]=j-1;dp[i][j]=dp[i-1][q[head]]+j*a[i]; }}ll ans=0;for(int i=1;i<=m;i++){ans=max(ans,dp[n][i]);}printf("%lld",ans);return 0;
}