Miku

线性dp+单调队列优化

单独的线性dp很好想，也很好卡。需要用单调队列优化。

对于1~l-1的点，他们是不可能到达的，（当然还有，不过因此for从l开始）。初始化dp为一个大负数，因为有negative答案

然后从l~n枚举（这里是要算dp的点），画个图就很好理解，单调队列扫到的点和枚举的点不一样。

队列里存的是dp，不是原值，这个很好理解。

惨痛教训：
过于依赖stl的我手写队列第一次挂了（边界晕了）

#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int q[200001];
long long dp[2000001];
long long  v[2000001];
int n,l,r;
int h,t;
int p;
long long ans;
int main(){
    scanf("%d%d%d",&n,&l,&r);
    for(int i=0;i<=n;++i){
        scanf("%lld",&v[i]);
    }
    memset(dp,-0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=l;i<=n;++i){
        while(h<=t&&q[t]<=dp[p])
            t--;
        t++;
        q[t]=dp[p];
        while(t-h+1>r-l+1)
        h++;
        dp[i]=q[h]+v[i];
        p++;
    }
    ans=-0x7f7f7f;
    for(int i=n-r+1;i<=n;++i){
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}