算法简介：寒苦回向

首先看名字就知道这是一个基于 单调队列 的动态规划，请先确保对于这个基础知识点理解无误再阅读下面的文章。

单调队列优化 DP 基于一些题目的单调性使用单调队列以达到降低 DP 维度等的优化作用。

算法演示：起死回骸

首先，为了保证大家对于单调队列的理解我们首先以一道单调队列的题目来回顾一下。

例题选讲 · 壹：冻冻回魂夜

题目描述

大秦为你打开 题目传送门

一个含有 n 项的数列，求出每一项前的 m 个数到它这个区间内的最小值。若前面的数不足 m 项则从第 1 个数开始，若前面没有数则输出 0 。

这道题首先肯定是一眼单调队列了，~~为了断掉各位数据结构大神的念想~~ RMQ 是不可能的~~（似乎卡常也可以哎貌似）~~。我们就按照这个单调队列的思路走就是了具体是真没什么难度。

代码也不放了。

那么接下来就是单调队列优化DP的内容了。

例题选讲 · 贰：云来古剑法

首先我们大可以先了解动态规划优化 DP 的原理。我们想到，单调队列中有这样的一个处理流程：

在窗口内处理的这些决策，有两种情况：

被排除的不合格决策。内层循环j排除的不合格决策，在外层循环i增大时，需要重复排除。
未被排除的决策。内层j未排除的决策，在外层i增大时，仍然能按原来的顺序被用到。

那么可以用单调队列统一处理这些决策，从而精简到只用一个循环，得到优化。

大概就是这样，接下来看看题目加深理解。

大秦为你打开 题目传送门

在一年前赢得了小镇的最佳草坪比赛后，Farmer John 变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，Farmer John 希望能够再次夺冠。

然而，Farmer John 的草坪非常脏乱，因此，Farmer John 只能够让他的奶牛来完成这项工作。Farmer John 有 $N$（$1\le N\le 10^5$）只排成一排的奶牛，编号为 $1\ldots N$。每只奶牛的效率是不同的，奶牛 $i$ 的效率为 $E_i$（$0\le E_i\le 10^9$）。

靠近的奶牛们很熟悉，因此，如果 Farmer John安排超过 $K$ 只连续的奶牛，那么，这些奶牛就会罢工去开派对 :)。因此，现在 Farmer John 需要你的帮助，计算 FJ 可以得到的最大效率，并且该方案中没有连续的超过 $K$ 只奶牛。

那么这道题我们怎么思考呢？我们不难想到，每 $k$ 个奶牛一定有一个选不了。也就是说，这些点中，至少存在一个断点 $j$ 。

我们设 $dp[i]$ 表示前 $i$ 个奶牛造成的最大价值，那么当节点 $j$ 为断点时，转移方程为：

$dp[i] = \max_{i-k\le j\le i}\{dp[i], dp[j - 1] + a[j+1]+\dots +a[i]\}$

处理出前缀和以后就变成了：

$dp[i] = \max_{i-k\le j\le i}\{dp[i], dp[j - 1] + sum[i]-sum[j]\}$

i由于我们枚举出了 $i$ 那么其实上，这个 $sum[i]$ 就是一个常量，我们可以把它提取出来。

$dp[i] = \max_{i-k\le j\le i}\{dp[i], dp[j - 1] -sum[j]\}+sum[i]$

这时候，我们就发现，转移方程只和 $j$ 有关了，，，这时候就是单调队列拍上去就过了。。。

然后就是代码部分：

for(int i = 1; i <= n; i++) {
    // 观察转移方程，我们要求的最大值形如 dp[i - 1] - sum[i];
	d[i] = dp[i - 1] - sum[i];
    // 这里就是单调队列维护较大值的板子
    while(hd <= tl && d[q[tl]] < d[i]) tl--;
    q[++tl] = i;
    while(hd <= tl && q[hd] < i - k) hd++;
    // 转移方程的内容了属于是
    dp[i] = d[q[hd]] + sum[i];
}