求调

TLYK2021001 @ 2024-11-21 14:56:19

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int n,l,r,a[300010],head,tail,d[300010];
int q[300010],ans=-inf,num[300010];
int main(){
    scanf("%d%d%d",&n,&l,&r);
    for(int i=0;i<=n;i++)scanf("%d",&a[i]);
    head=tail=1;
    for(int i=l;i<=n;i++){
        while(num[head]<i-r)head++;
        while(head<=tail&&q[tail]<=d[i-l])tail--;
        q[++tail]=d[i-l];
        num[tail]=i-l;
        d[i]=q[head]+a[i];
    } 
    for(int i=n-r+1;i<=n;i++)ans=max(ans,d[i]);
    printf("%d\n",ans);
    return 0;
}

by TLYK2021001 @ 2024-11-21 14:57:33

https://www.luogu.com.cn/record/190135995

by TLYK2021004 @ 2024-11-21 15:12:24

@TLYK2021001高彪別慌，讓我幫你看看

by TLYK2021004 @ 2024-11-21 16:13:34

@TLYK2021001改好了

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int n,l,r,a[200010],head,tail,d[200010],c[200010];
int q[400010],ans=-inf,num[400010];
int main(){
    scanf("%d%d%d",&n,&l,&r);
    for(int i=0;i<=n;i++)scanf("%d",&a[i]),d[i]=-inf;
    head=tail=1;
    d[0]=0;
    c[0]=1;
    for(int i=l;i<=n;i++){

        while(head<=tail&&q[tail]<=d[i-l])tail--;
        q[++tail]=d[i-l];
        num[tail]=i-l;
        while(num[head]<i-r)head++;
        d[i]=q[head]+a[i];
        c[i]=c[num[head]];
    }
    for(int i=n-r+1;i<=n;i++)if(c[i])ans=max(ans,d[i]);
    printf("%d\n",ans);
    return 0;
}

by TLYK2021001 @ 2024-11-21 16:18:11

%%% 拜谢大佬已关