求助单调队列dp板子

P1725 琪露诺

abc_de @ 2022-09-02 22:36:40

wa两个测试点 80pts 求dalao帮忙看看 谢谢

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n,l,r;
int w[maxn];
int dp[maxn],ans=-0x3f3f3f3f;
struct node{
    int p,a;    
}q[maxn];
int rd(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();   
    }
    return x*f;
}
int main(){
//  freopen("A.in","r",stdin);
//  freopen("A.out","w",stdout);
    n=rd();l=rd();r=rd();
    for(int i=0;i<=n;i++) w[i]=rd();
    int l1=0,r1=0;
    for(int i=1;i<=n+r;i++) dp[i]=-0x3f3f3f3f;
    for(int i=l;i<=n+r;i++){
        while(l1<=r1&&q[r1].p>i-l) r1--;
        while(l1<=r1&&q[l1].p<i-r) l1++;
        dp[i]=q[l1].a+w[i];
        while(l1<=r1&&dp[i-l+1]>q[r1].a) r1--;
        q[++r1].a=dp[i-l+1];
        q[r1].p=i-l+1;
    }
    for(int i=n+1;i<=n+r;i++) ans=max(ans,dp[i]);
    cout<<ans;
    return 0;   
}

|