题目链接
P2034 选择数字
题目分析
贪心想法及其问题
要使得“不能有超过$k$个连续的数被选中”，
可以转化为：
在$k+1$个连续的数中，选择一个数舍去，断开成两个小于$k$个连续的数。
再从断开的节点往后$k+1$个连续的数中，再选择一个数断去。
刚开始很容易想到一种贪心的思路。
每次选择最小的数舍去。
但证明其正确性（是否会反悔）时，
发现是存在反悔情况的。
对于数据：
8 5 2 100 ∞ ∞ ∞ ∞ ∞ 1若采用上述贪心，则会舍去$2,100,1$三个数。
但实际最开始的$2$并不用舍去，造成了反悔情况。
如果写带反悔的贪心可能过于复杂，
所以这里直接退用动态规划来写。
动态规划想法
动态转移方程推导
记：$dp[i]$为前面$i$项最优的解。
对于$dp[i]$，有以下几种取值情况：
-
不选择第$i$项。
直接用前面的最优的解。
即为：$dp[i-1]$。 -
选择第$i$项。
则需从前面$k$项中，任选第$j$项舍去，
并取所有选择中的最优情况。舍去第$j$项后，值为$\sum_{t=j+1}^{i-1}a[t]+dp[j-1]+a[i]$（即前面第$j+1 \sim i-1$项的和，加上$dp[j-1]$）
最优情况即为：$\max(\sum_{t=j+1}^{i-1}a[t]+dp[j-1]+a[i]) (j∈[i-k,i-1])$。
综上，动态转移方程为：
$$dp[i]=\max(dp[i-1],\max(\sum_{t=j+1}^{i-1}a[t]+dp[j-1]+a[i] (j∈[i-k,i-1])))$$
最后答案即为$dp[n]$。
单调队列优化
对于方程中的$\max(\sum_{t=j+1}^{i-1}a[t]+dp[j-1]+a[i] (j∈[i-k,i-1]))$，
如果每次都用for遍历$j$来求得，肯定喜得TLE。
在之前分析过程中，我们就能隐约感觉到：
这个找前$k$项中的最优情况，
跟之前做过的滑动窗口这道题有点像！
其思想就是单调队列。
用单调队列，来记录前面$k$项中的$\sum_{t=j+1}^{i-1}a[t]+dp[j-1]$（没包含$a[i]$）的情况。
窗口移动到$i$时，队列新增(push)的项就为$dp[i-1]$（因为此时$j=i-1$，$\sum$值为$0$)。
但这里需要注意：
当窗口移动时，窗口内所有项的$\sum$的值会变，
其均会增加 新移动到的这项$a[i]$。
但如果直接在单调队列中所有项进行增加，则又会回到$O(n^2)$的复杂度。
因此可以用个变量$inc$，记录窗口中所有项要增加的值，
每移动次窗口，就让inc+=a[i]。
在计算$dp[i]$时，再加上$inc$即可，
即将动态转移方程变为了：
$$dp[i]=max(dp[i-1],top+inc+a[i])$$
其中$top$表示优先队列中首项。
然后又要注意：
在入队push的时候，需要减去$inc$的值，
即push(dp[i-1]-inc)。
否则在计算$dp[i]$的$top+inc+a[i]$时，
会多加$inc$的值。
然后对于最开始的$1 \sim k$项来说：
舍弃第$j$项的最优情况，就是前$k$项的和减去$a[j]$。
所以可以先让$inc=\sum_{i=1}^ka_i$，
则每次push(-val[i])，
加上$inc$后，即为最开始$k$项的最优情况。
个人代码
//P2034 [选择数字](https://www.luogu.com.cn/problem/P2034)
#include <bits/stdc++.h>
#define ALL(NAME_i, BEGIN, TO) \
int NAME_i = BEGIN; \
NAME_i <= TO; \
NAME_i++
using namespace std;
typedef long long LL;
#define MAX_N 100000
int val[MAX_N + 5]; //*可优化这个空间，因为不用记录读入的值
LL dp[MAX_N + 5]; //dp[i] - 前i个数最优情况
struct windowType
{
int head = 1, tail = 0;
struct lineType
{
LL val;
int index;
lineType() : val(0), index(0) {}
lineType(LL _val, int _index) : val(_val), index(_index) {}
} line[MAX_N + 5];
LL top() { return line[head].val; }
void push(const LL &val, const int &index)
{
while (head <= tail && val > line[tail].val)
tail--;
line[++tail] = lineType(val, index);
}
void update(const int &range)
{
if (line[head].index < range)
head++;
}
} window; //单调队列——记录前k个中最优的选择（去除某点后的结果）
LL inc; //单调队列中每个元素要加的值
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for (ALL(i, 1, k))
scanf("%d", &val[i]), dp[i] = dp[i - 1] + val[i], window.push(-val[i], i); //对最开始k项的处理 - 直接push(-a[i])
inc = dp[k]; //对最开始k项的处理 - 刚开始的inc令为sum(a[1]~a[k])
for (ALL(i, k + 1, n))
{
scanf("%d", &val[i]); //0. 读入a[i]
dp[i] = max(dp[i - 1], window.top() + inc + val[i]); //1. 动态转移方程计算dp
inc += val[i]; //2. inc += val
window.push(dp[i - 1] - inc, i); //3. 入队
window.update(i - k + 1); //4. 出队 - 维护队首
}
printf("%lld", dp[n]);
return 0;
}
/* WA 记录：
1st. 单调队列中出队的过程写错了，
不能直接判断窗口是否满了，而要看是否超出窗口范围。
*/