蜜汁错误，样例过了，结果全WA，求好心的大佬帮忙看看

HGJH°L @ 2020-12-01 22:05:49

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f
#define lowbit(x) x & -x
#define re register

using namespace std;

int n;
int l,r;
int a[200005];
int ans[200005];
int que[200005];
int head=1,tail=1;
int maxn=-INF;
int i,j;

int main(int argc,char** argv)
{

    cin >>n;
    cin >>l>>r;
    memset(ans,128,sizeof(ans));
    ans[0]=0;
    for (i=0;i<=n;i++)
        cin >>a[i];
    for (i=l;i<=n;i++)
    {
        while (ans[i-l]>=ans[que[tail]]&&tail>=head)
            tail--;
        que[++tail]=i-l;
        while (que[head]+r<i)
            head++;
        ans[i]=ans[que[head]]+a[i];
        if (i+r>n)
            maxn=max(maxn,ans[n-i+1]);
    }
    cout <<maxn<<endl;
    return 0;
}

by qpdk777 @ 2020-12-04 21:42:45

hack1

input:
5 3 5
16 19 4 10 1 11 

output:
26

wrong answer:
10

hack2

input:
10 1 7
17 13 10 16 14 8 2 10 4 7 7 

output:
108

wrong answer:
61

hack3

input:
20 6 16
15 6 17 1 5 8 3 11 12 17 7 19 6 18 1 5 17 8 3 18 14 

output:
62

wrong answer:
17

给你几组hack，你自己调一调吧。

NOIP2020 RP++!!!

by HGJH°L @ 2020-12-04 21:48:06

@HClOVE 大佬，实在调不出来，您能直接指出蒟蒻的烂代码究竟哪里出了问题？谢谢qwq

by qpdk777 @ 2020-12-04 22:01:03

@CR_HGJH

1. 一般情况下，我们通常把“排除过时决策”写在“排除不优决策并插入新决策”之前，建议你改过来；
2. 凡是涉及出队/入队操作，都要保证 tail>=head ，请你在第二个 while 里加上；
3. ans[0]=0; 是错的！应为 ans[0]=a[0] ，因为题目不保证 a[0]==0 ；
4. 先把所有dp做完再统计 maxn ；
5. 注意大于号小于号要不要加等号。
6. 你的队列是包含两端点的，所以初始化为 head = 1, tail = 0;

by HGJH°L @ 2020-12-04 22:20:18

@HClOVE 谢谢大佬，过了（虽然好多不是照着您说的改的，但还是十分感谢您）

PS：顺便说一下，您给的第一个数据应该是27而不是26

by HGJH°L @ 2020-12-04 22:20:34

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f
#define lowbit(x) x & -x
#define re register

using namespace std;

int n;
int l,r;
int a[200005];
int ans[200005];
int que[200005];
int head=1,tail=1;
int maxn=-INF;
int i,j;

int main(int argc,char** argv)
{

    cin >>n;
    cin >>l>>r;
    memset(ans,128,sizeof(ans));
    for (i=0;i<=n;i++)
        cin >>a[i];
    ans[0]=a[0];
    for (i=l;i<=n;i++)
    {
        while (ans[i-l]>=ans[que[tail]]&&tail>=head)
            tail--;
        tail++;
        que[tail]=i-l;
        while (que[head]+r<i)
            head++;
        ans[i]=ans[que[head]]+a[i];
        if (i+r>n)
            maxn=max(maxn,ans[i]);
    }
    cout <<maxn<<endl;
    return 0;
}