求助全WA

P1725 琪露诺

Kniqht @ 2020-12-13 14:04:11


#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,l,r,ans,q[N],hh,tt,f[N],a[N];
int main(){
    memset(f,0xcf,sizeof(f));//赋值
    f[0]=0,ans=f[1];
    scanf("%d%d%d",&n,&l,&r);
    scanf("%d",&a[0]);
    for(int i=1;i<=n;i++) 
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        while(hh<=tt&&q[hh]+r-1>=i&&q[hh]+l-1<=i) hh++;//hh<=tt队列非空,后两个是越界判断
        f[i]=max(f[i],f[q[hh]]+a[i]);//dp
        while(hh<=tt&&f[q[tt]]<f[q[i]]) tt--;//更新
        q[++tt]=i;/入队
    }
    for(int i=n-r+1;i<=n;i++) ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
}```

|