修剪草坪

LibreOJ-10177-修剪草坪

实现

#include <iostream>
#include <queue>
using namespace std;

typedef long long LL;
const int N = 100010;
int n, k;
int e[N];
LL sum[N], f[N];

LL g (int idx) {
    return f[idx - 1] - sum[idx];
}

int main () {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++ i) scanf("%d", &e[i]);

    for (int i = 1; i <= n; ++ i) sum[i] = sum[i - 1] + e[i];
    deque<int> dq;
    dq.push_back(0);
    for (int i = 1; i <= n; ++ i) {
        if (!dq.empty() && i - dq.front() > k) dq.pop_front();
        f[i] = max(f[i - 1], g(dq.front()) + sum[i]);
        while (!dq.empty() && g(dq.back()) <= g(i)) dq.pop_back();
        dq.push_back(i);
    }
    printf("%lld", f[n]);
    return 0;
}