[題解]（單調隊列dp）luogu_P1725琪露諾

佚名 5年前 (2019-04-23) 随笔 1647人围观抢沙发百度已收录

比較簡單的單調隊列，但是有一些要注意的

維護單調隊列的時候裡面存的是入隊時間，而不是i，因為前面有l個沒有入隊（不可能走進），所以把i减一个l以达到延迟入队的效果

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
int n,l,r,a[maxn];
int q[maxn],head=1,tail=0;
int f[maxn];
int main()
{
    scanf("%d%d%d",&n,&l,&r);
    for(int i=0;i<=n;i++)scanf("%d",&a[i]);
    for(int i=l;i<=n;i++){
        while(head<=tail && q[head]+r<i)head++;
        while(head<=tail && f[q[tail]]<f[i-l])tail--;
        q[++tail]=i-l;//不能直接用i,不然記個p當做時間也行(一樣效果 
        f[i]=f[q[head]]+a[i];
    }
    int ans=0;
    for(int i=n+1-r;i<=n;i++)ans=max(ans,f[i]);
    printf("%d",ans);
}