「USACO 2011」修剪草坪

题目大意：给定 $n$ 个连续的点，每个点有一个权值 $v_i$，不能选取连续的超过 $k$ 个点，问最大收益。$n \leq 100000, 0 \leq v_i \leq 10^9$

设 $f[i]$ 表示 $i$ 不选且之前的选取都合法情况下答案损失的最小值，有

$$f[i]=f[j]+v[i]\ (i-j\leq k)$$

#include <cstdio>
#include <algorithm>

using std::max;

typedef long long LL;
const int N = 100005;
int a[N], q[N], head = 1, tail, n, k; LL f[N], ans, sum;

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), sum += a[i];
    for (int i = 1; i <= k + 1; ++i) {
        f[i] = a[i];
        while (head <= tail && f[q[tail]] >= f[i]) --tail; //不要忘记更新
        q[++tail] = i;
    }
    for (int i = k + 2; i <= n; ++i) {
        while (head <= tail && q[head] + k + 1 < i) ++head;
        f[i] = f[q[head]] + a[i];
        while (head <= tail && f[q[tail]] >= f[i]) --tail;
        q[++tail] = i;
    }
    for (int i = n - k; i <= n; ++i) ans = max(ans, sum - f[i]);
    printf("%lld\n", ans);
    return 0;
}

时间复杂度 $O(n)$