Luogu P2034 选择数字

题目描述

https://www.luogu.com.cn/problem/P2034

Solution

为了方便进行 $dp$，我们定义 $f_i$ 表示不选第 $i$ 的最大值

那么显然有以下转移 $f_i=max\{f_j+s_{i-1}-s_j\}$，其中 $i-j-1\le m$

我们把 $s_{i-1}$ 提出来，后面那个东西显然可以拿单调队列维护

时间复杂度 $O(n)$

#include <iostream>
#include <cstdio>
#define maxn 100010
#define ll long long 
using namespace std;

int n, m, a[maxn];

ll f[maxn], s[maxn];

struct Queue {
    int k; ll v;

    Queue(int _k = 0, ll _v = 0) { k = _k; v = _v; } 
} Q[maxn]; int h, t; 

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), s[i] = s[i - 1] + a[i];
    Q[h = t = 1] = Queue(0, 0); 
    for (int i = 1; i <= n + 1; ++i) {
        while (h < t && i - Q[h].k - 1 > m) ++h;
        f[i] = Q[h].v + s[i - 1];
        while (h <= t && f[i] - s[i] > Q[t].v) --t;
        Q[++t] = Queue(i, f[i] - s[i]); 
    } 
    cout << f[n + 1] << endl;
    return 0;
}