题目大意
给定 \(n\) 个非负整数 \(a_1 \cdots a_n\)。现在你可以选择其中若干个数，但不能有超过 \(k\) 个连续的数字被选择。
求选出的数字的和最大。
思路简析
一个比较好的思路是反向思考：选择某些间隔小于等于 \(k\) （相邻间隔为 \(0\)）的数字，求选择的数字的最小值。
但是我没看明白。
所以顺推并分讨：有两种情况：在前 \(i\) 个数中不选择/选择第 \(i\) 个数时的最大值，分别用 \(f_{i, 0}\) 和 \(f_{i, 1}\) 表示。
\[f_{i, 0} = \max\{f_{i-1, 0}, f_{i-1, 1}\} \]\[f_{i, 1} = \max_{j=i-k}^{i-1}\{f_{j, 0}+a_{j+1}+\cdots + a_i\} \]考虑使用前缀和优化，则第二个式子可化简为：
\[\begin{split} f_{i, 1} &= \max_{j=i-k}^{i-1}\{f_{j, 0}+sum[i]-sum[j]\} \\ &= \max_{j=i-k}^{i-1}\{f_{j, 0}-sum[j]\} +sum[i]\} \end{split} \]这样就是要动态地维护一个区间内的最大值，因此使用单调队列。
每次的维护区间为 \(i-k \sim i-1\)，并不包含 \(i\)，所以应先弹出不合规的队首，然后更新 \(f_{i, 0}\) 和 \(f_{i, 1}\)，最后在保证单调性的同时将当前 \(i\) 加入队列。
CODE
Time complexity：\(\Omega(n)\)。
#include <bits/stdc++.h>
namespace {
#define filein(x) freopen(x".in", "r", stdin)
#define fileout(x) freopen(x".out", "w", stdout)
#define files(x) filein(x), fileout(x)
using namespace std;
#define ll long long
#define db double
const int man = 1e5+10;
}
int n, m;
ll sum[man], f[man][2];
int a[man];
deque <int> dq;
int main () {
#ifndef ONLINE_JUDGE
files("test");
#endif
scanf("%d%d", &n, &m);
dq.push_back(0);
for (int i = 1; i <= n; ++ i) {
scanf("%d", a+i), sum[i] = sum[i-1]+a[i];
while (dq.size() && i-dq.front()>m) dq.pop_front();
f[i][0] = max(f[i-1][0], f[i-1][1]);
if(!dq.empty()) f[i][1] = f[dq.front()][0]-sum[dq.front()]+sum[i];
while (dq.size() && f[i][0]-sum[i]>f[dq.back()][0]-sum[dq.back()]) dq.pop_back();
dq.push_back(i);
} printf("%lld", max(f[n][0], f[n][1]));
return 0;
}