hack过不去,求指点

P1725 琪露诺

ananran998 @ 2023-06-08 16:29:13

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<#x<<":"<<x<<endl
const int N = 2e5 + 1;

int n, a[N], f[N];
char s[1002];

int q[N], front = 1, rear = 0;

inline void solve() {
    int L, R;
    scanf("%d%d%d", &n, &L, &R);
    for (int i = 0; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        f[i] = -1;
    f[0] = 0;
    q[++rear] = 0;
    int k = 0;
    for (int i = L; i <= n; i++) {
        if (!(abs(q[front] - i) >= L && abs(q[front] - i) <= R))
            ++front;
        if (front <= rear && abs(q[front] - i) >= L && abs(q[front] - i) <= R)
            f[i] = f[q[front]] + a[i];
        // debug(i), debug(front), debug(rear), debug(q[front]);
        ++k;
        while (front <= rear && f[k] >= f[q[rear]])
            --rear;
        q[++rear] = k;
    }
    for (int i = n - R + 1; i <= n; i++)
        f[n] = max(f[n], f[i]);
    // for (int i = 1; i <= n; i++)
    //  printf("i : %d, f[i] : %d\n", i, f[i]);
    printf("%d\n", f[n]);
}

//0 12 3 11 7 -2
/*
5 3 4
0 1 2 3 4 5
*/

int main() {
    int t;
    // cin >> t;
    t = 1;
    while (t--)
        solve();

    return 0;
}
// 1 5 6 7 2 10 9 8 4 3 1

by Aisaka_Taiga @ 2023-06-14 15:34:46

@ananran998 你的初始值太大了,f设为一个极小值比如-0x3f3f3f3f就过了


|