单调队列dp求助

P1725 琪露诺

小超手123 @ 2022-08-31 15:57:51

#include<bits/stdc++.h>
using namespace std;
int n,l,r,ans=-1e9,a[300005],f[300005]; //f[i]表示跳到i 
int que[300005],head=1,tail=0; //head~tail
int main() {
    scanf("%d %d %d",&n,&l,&r);
    for(int i=0;i<=n;i++){
        scanf("%d",&a[i]);
        f[i]=-1e9;
    }
    f[0]=0;
    for(int i=0;i<l;i++)
    for(int i=0;i<=n;i++){
        //单调队列求最大值(i-r~i-l) 
        while(tail>=head&&i-que[head]+1>r-l+1)head++; //过期的
        while(tail>=head&&f[que[tail]]<f[i-l+1]&&i>=l)tail--;
        que[++tail]=i-l+1;
        f[i]=f[que[tail]]+a[i];
        /*for(int j=i-r;j<=i-l;j++){  //j->i
            if(j>=0)
                f[i]=max(f[i],f[j]+a[i]);
        }*/
        if(i>=n-r+1)
            ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;   
}

|