单调队列求助100pts但hack数据过不去

P1725 琪露诺

Aakkosetsumussa @ 2023-07-17 10:52:59

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,l,r,a[30000000],m[30000000],mx=-0x3f3f3f3f,q[30000000],head=1,tail=1;
int main() {
    scanf("%lld %lld %lld",&n,&l,&r);
    for(ll i=0; i<=n; i++)
        scanf("%lld",&a[i]);
    for(ll i=l; i<=n; i++) {
        while(head<=tail&&m[q[tail]]<=m[i-l])
            tail--;
        q[++tail]=i-l;
        while(q[head]+r<i)
            head++;
        m[i]=m[q[head]]+a[i];   
    }
    for(ll i=n+1-r; i<=n; i++)
        mx=max(mx,m[i]);
    printf("%lld\n",mx);
    return 0;
}

by Qwdb @ 2023-08-11 10:34:12

需要把dp数组初始化为极小值。

就是在开头加上:

memset(m, 0xcf, sizeof m);
m[0] = 0;

不妨试试这组hack数据:

10 5 6 
0 10 2 13 24 -5 -6 1 0 3 -1

正确答案应该是5


by Qwdb @ 2023-08-11 10:34:45

啊不对正确答案是-5


by Qwdb @ 2023-08-11 10:37:03

哦然而你用的是long long,那就不能memset了,就for循环赋一个极小值就好了


by Qwdb @ 2023-08-11 10:38:46

酱紫

for(int i=1;i<=3000000;i++)
{
    m[i]=-2147483648;
}

by littlebug @ 2023-08-17 18:59:18

可以memset吧

memset(m,-0x3f,sizeof(m));

|