求助一个关于Subteck2的问题

P1725 琪露诺

卷王 @ 2022-11-29 19:30:41

为什么要把 f_i 初始化为 0xcf 呢?

Subteck2 全错代码:

#include <bits/stdc++.h>
using namespace std;
int n, l, r, ans = -10000000;
int a[200001], f[200001];
int q[200001]; //优先队列 
int main()
{
    cin >> n >> l >> r;
    for(int i = 0; i <= n; i++)
        cin >> a[i];
    //memset(f, 0xcf, sizeof(f));
    //f[0] = 0;
    int head = 0, tail = -1;
    for(int i = l; i <= n; i++)
    {
        while(head <= tail && q[head] < i - r) head++;
        while(head <= tail && f[i - l] > f[q[tail]]) tail--;
        q[++tail] = i - l;
        f[i] = f[q[head]] + a[i];
    }
    for(int i = n + 1 - r; i <= n; i++)
        ans = max(ans, f[i]);
    cout << ans;
    return 0;
}

Subteck2 全对代码:

#include <bits/stdc++.h>
using namespace std;
int n, l, r, ans = -10000000;
int a[200001], f[200001];
int q[200001]; //优先队列 
int main()
{
    cin >> n >> l >> r;
    for(int i = 0; i <= n; i++)
        cin >> a[i];
    memset(f, 0xcf, sizeof(f));
    f[0] = 0;
    int head = 0, tail = -1;
    for(int i = l; i <= n; i++)
    {
        while(head <= tail && q[head] < i - r) head++;
        while(head <= tail && f[i - l] > f[q[tail]]) tail--;
        q[++tail] = i - l;
        f[i] = f[q[head]] + a[i];
    }
    for(int i = n + 1 - r; i <= n; i++)
        ans = max(ans, f[i]);
    cout << ans;
    return 0;
}

by z_y_ @ 2022-11-29 19:55:05

@holdyhao_Genius 冰冻指数可能为负,所以要把f初始为负无穷


by z_y_ @ 2022-11-29 19:56:08

还有q应该是单调队列吧


by 卷王 @ 2022-11-29 20:30:51

@zy 哦对,我是蒟蒻


by 卷王 @ 2022-11-29 20:35:45

@zy 0xcf 我是看题解里有人用的,转了一下怎么是207啊???

(我用http://hex.babihu.com/id/16100xcf.html搞的,一种偷懒的方法


by 卷王 @ 2022-11-29 20:37:12

@zy


by z_y_ @ 2022-11-29 20:56:43

@holdyhao_Genius memset是以单个字节为一个单位赋值的,而int是4个字节,赋值时会把一个int所占的四个字节内存都给赋值为0xcf(207),也就是说每个int里的数就是0xcfcfcfcf(11001111110011111100111111001111),而C++二进制最高位为符号位,'1'表示负,所以就初始化为了一个极大负数。


by 卷王 @ 2022-11-30 17:56:00

@zy 哦明白了。


|