求助大佬，这个为什么只能AC一半啊

ShuF @ 2024-04-14 17:38:58

#include<bits/stdc++.h>
using namespace std;

int N,L,R;
int f[20005];int num[20005];
struct PII{
    int num;int time;
};
deque<PII> dq;
void go_in(int n,int i){
    PII t;
    if(!dq.empty()){
        if(dq.front().time<i-R+1) dq.pop_front();
    }
    while(!dq.empty() && dq.back().num <= n) dq.pop_back();
    t.num=n;t.time=i;dq.push_back(t);
}

void solve(){
    int ans=-1e8;
    cin>>N>>L>>R;
    for(int i=0;i<=N;i++){
        cin>>num[i];
    }

    memset(f, 0x80, sizeof(f));

    f[0]=0;

    for(int i=L;i<=N;i++){//L前的位置无法到达，默认为负无穷
        go_in(f[i-L],i-L);//求l时，l只能由0过来，所以推出来每次入队列是i-L
        int from=dq.front().time;//最大的数据

        f[i]=f[from]+num[i];

        if(i+R > N ) ans=max(ans,f[i]);     
    }
    cout<<ans<<endl;

}

int main(){
    solve();
}

by ShuF @ 2024-04-14 17:41:47

@ShuF 把数组改大了，现在就剩下Subtask2的两个数据过不去了

by NKOJ_AKer @ 2024-04-14 17:56:53

哪一题啊

by qfcxxcfrpig_FOROG @ 2024-04-14 18:05:26

@Andywang112358 你眼睛没有吗？

by Super_Cube @ 2024-04-14 18:44:18

@ShuF 改好了，代码如下。

#include<bits/stdc++.h>
using namespace std;

int N,L,R;
int f[200005];int num[200005];
struct PII{
    int num;int time;
};
deque<PII> dq;
void go_in(int n,int i){
    PII t;
    while(!dq.empty()&&dq.front().time<=i+L-R+1) dq.pop_front();
    while(!dq.empty() && dq.back().num <= n) dq.pop_back();
    t.num=n;t.time=i;dq.push_back(t);
}

void solve(){
    int ans=-2e9;
    cin>>N>>L>>R;
    for(int i=0;i<=N;i++){
        cin>>num[i];
    }

    memset(f, 0x80, sizeof(f));

    f[0]=num[0];

    for(int i=L;i<=N;i++){//L前的位置无法到达，默认为负无穷
        go_in(f[i-L],i-L);//求l时，l只能由0过来，所以推出来每次入队列是i-L
        int from=dq.front().time;//最大的数据

        f[i]=f[from]+num[i];

        if(i+R > N ) ans=max(ans,f[i]);     
    }
    cout<<ans<<endl;

}

int main(){
    solve();
}

by ShuF @ 2024-04-14 19:08:43

@Super_Cube 谢谢大佬，我太菜了，入队列这里判队列长度错了硬是没看出来，这么关键的错误居然还能ac掉subtask1

by NKOJ_AKer @ 2024-05-05 15:44:59

@qfcxxcfrpig_FOROG 孩子，你没有无敌吗？

by qfcxxcfrpig_FOROG @ 2024-05-05 17:16:22

@Andywang112358 你sb吧自己没长眼还海底捞对线