琪露诺

题目传送门

解题思路

这题和烽火传递（单调队列）差不多
只不过这个是单调递减（第一位是最大值）
烽火传递是单调递增（第一位是最小值）

AC代码

#include<iostream>
using namespace std;
long long n,l,r,s,head,tail,a[200005],p[200005],f[200005];
int main()
{
   
	cin>>n>>l>>r;
	for(int i=0;i<=n;i++)//从0开始
	 cin>>a[i],f[i]=-2147483647;
	head=1;//初值
	f[0]=0;
	s=-2147483647;
	for(int i=1;i<=n;i++)
    {
   
    	if(i>=l)//避免i-l为负数
        {
   
        	while(f[i-l]>=f[p[tail]]&&head<=tail)tail--;//队尾弹出
        	p[++tail]=i-l;//进队
        }
        while(p[head]<i-r&&head<=tail)head++;//队头弹出 
        if(head<=tail)f[i]=f[p[head]]+a[i];//状态转移
    }
    for(int i=n-r+1;i<=n;i++)
	 s=max(s,f[i]);//max最大值
    cout<<s;
}

谢谢