关于单调队列初始化

P2627 [USACO11OPEN] Mowing the Lawn G

Z3k7223 @ 2024-04-09 13:52:51

这份代码的初始化是 head = 1, tail = 0 (样例没过),但是提交喜提 10pts,只要把初始化改为 head = 1, tail = 1 就能 AC,求问原因,玄关感谢。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n, k;
int a[N], sum[N], f[N][2];
int p[N], q[N], head = 1, tail;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        f[i][0] = max(f[i - 1][0], f[i - 1][1]);
        f[i][1] = q[head] + sum[i];
        while (head <= tail && q[tail] < f[i][0] - sum[i]) {
            --tail;
        }
        q[++tail] = f[i][0] - sum[i];
        p[tail] = i;
        while (head <= tail && p[head] < i - k + 1) {
            ++head;
        }

    }
    cout << max(f[n][0], f[n][1]) << '\n';
    return 0;
}

by zzxLLL @ 2024-04-09 14:56:01

其他点应该可以从 f_0 转移过来


|