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