蒟蒻求助

P1725 琪露诺

forest114514 @ 2023-07-17 15:33:01

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2*1e5+100;
int n,l,r;
int a[N],f[N],q[N],head=1,tail=0;
int main(){
    int maxx=-0x3f3f3f3f;
    cin>>n>>l>>r;
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    for(int i=0;i<=n;i++) cin>>a[i];
    for(int i=l;i<=n;i++){
        while(i-q[head]>r&&head<=tail)head++;
        while(f[i-l]>f[q[tail]]&&head<=tail)tail--;
        q[++tail]=i-l;//为什么这句放在18行就会错??? 
        f[i]=f[q[head]]+a[i];

    } 
    for(int i=n-r+1;i<=n;i++) maxx=max(maxx,f[i]);
    cout<<maxx<<endl;

    return 0;
}

by forest114514 @ 2023-07-17 15:34:23

为什么把“q[++tail]=i-l;”这一句放在f[i]=f[q[head]]+a[i];后面就会错呀,有没有大佬能解答一下


by LgxTpre @ 2023-07-17 15:38:03

@zybyydsb 因为你可能把旧决策都弹出了,还没加新决策怎么直接更新答案


by forest114514 @ 2023-07-17 19:07:48

谢谢大佬Orz


|