卷王 @ 2022-11-29 19:30:41
为什么要把
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 哦明白了。