单调队列优化dp
XyzL
2020-08-25 16:50:15
## 前置知识：
1：**基础DP**
2：**单调队列的运用**
## 何为单调队列？
从字面意思上来看，无非就是有某种**单调性**的队列。
一般的解释是 “不断地向缓存数组里读入元素，也不时地去掉最老的元素，不定期的询问当前缓存数组里的最小/大的元素。”
其实本质上就是一种特殊的**双端队列**，一般解决类似于[滑动窗口](https://www.luogu.com.cn/problem/P1886)的最值问题。
那么我们应该如何去维护这样一个单挑队列呢？
------------
## 如何解决？
以上题为例，
题意为给定一个序列 $a$ ，一个长度为 $k$ 的窗口，窗口从左至右滑动，求每个区间的大小最值。
### 方法1：朴素算法（暴力）
我们可以对每个区间进行直接扫描，每次枚举元素 $a_x$ 至 元素 $a_{x+k-1}$ 的最大值和最小值，时间复杂度为 $O(nk)$ 。
### 方法2： $RMQ$ 和线段树
熟悉数据结构的奆佬知道，显然这是个静态区间最值问题。
我们可以使用线段树等数据结构将此算法优化到 $O(n$ $log_2{n})$ ,虽然在此基础上还可以进行**修改**，但此题的 $n, k$ 为 $1e6$ ，显然会超时，这时候就可以用到我们的单调队列。
### 方法三： 单调队列
线段树和 $ST$ 算法都是求**任意长度**区间最值的通用算法，而这题有个很重要的信息，我们每次去询问的区间长度都是**固定**为 $k$ 的，且每个区间都是**连续**的，那么对于每两个“相邻”的区间 $(L, R)$ 与 $(L + 1, R + 1)$ ，都会存在以下性质：
$Max/Min$ {$a_L, a_{L+1}, a_{L+2}...,a_{R-1}, a_R$} $=$ $Max/Min$ $( a_L, $ $Max/Min$ {$a_{L+1}, a_{L+2}...,a_{R-1}, a_R$} $)$
$Max/Min$ {$a_{L+1}, a_{L+2}...,a_R, a_{R+1}$} $=$ $Max/Min$ $( $ $Max/Min$ {$a_{L+1}, a_{L+2}...a_{R-1},a_R$}, $a_{R+1}$ $)$
经过观察得，两个方程都有相同的地方 ：$a_{L+1}. a_{L+2}...,a_{R-1}, a_R$
所以，可以得出我们在求区间 $(L+1, R+1)$ 时，我们完全没有必要再扫描一次，只要当上一次的最值落在了 $a_L$ 上时，我们才需要重新扫描，这样，我们的算法就得到了极大地优化。
我们以最大值为例，对于任意的 $L≤i≤j≤R$ ，如果 $a_i<a_j$ ，那么我们的窗口在向右滑动时，最大值永远不会移动到 $a_i$。**因为** $a_i$ **会比** $a_j$ **先过期，而能用** $a_i$ **的时候，就一定可以用** $a_j$。**此时我们就可以不需要** $a_i$ **了。**
~~我们常说一句话：“奆佬 ，比我小，还比我强，我要被pop_back了。”这句话和很明显与单调队列的本质相符合~~。
我们可以拿[此题](https://www.luogu.com.cn/problem/P1886)的样例来看：
```
8 3
1 3 -1 -3 5 3 6 7
```
以最小值为例，我们将 $Q$ 表示为单调队列，$P$ 表示其所对应的在原列表里的序号。
1. 出现 $1$ 。此时队中没有元素，$1$ 进队。此时，$Q={1}; P={1}$。
2. 出现 $3$ 。是否可以进队？下面基于这样一个思想: 假如把 $3$ 放进去，如果后面 $2$ 个数都比它大，那么 $3$ 或许可以成为最小的。此时，$Q={1,3}; P={1,2}$
3. 出现 $-1$ 。队尾元素 $3$ 比 $-1$ 大，那么意味着只要 $-1$ 进队，那么 $3$ 必定成为不了最小值，原因很明显:因为当下面 $3$ 被框起来，那么 $-1$ 也一定被框起来，所以 $3$ 永远不能当最小值。所以， $3$ 从队尾出队。同理，$1$ 从队尾出队。最后 $-1$ 进队，此时 $Q={-1},P={3}$
4. 出现 $-3$ .同上面分析，$-1>-3$，$-1$ 从队尾出队, $-3$ 从队尾进队。$Q={-3};P={4}$。
5. 出现 $5$ 。因为 $5>-3$ ，同第二条分析， $5$ 或许可以成为最小值，所以 $5$ 进队。此时，$Q={-3,5};P={4,5}$
6. 出现 $3$ 。 $3$ 先与队尾的 $5$ 比较，$3<5$ ，按照第 $3$ 条的分析， $5$ 从队尾出队。 $3$ 再与 $-3$ 比较，同第二条分析，$3$ 进队。此时，$Q={-3,3};P={4,6}$
7. 出现 $7$ 。队尾元素 $6$ 小于 $7$ ，$7$进队。此时，$Q={3,6,7};P={6,7,8}$。
所以，当我们将窗口 $(L, R)$ 滑动到 $(L+1, R+1)$ 时，若队首元素不在 $(L+1, R+1)$ 的区间中，则删除，将 $a_{R+1}$ 插入进单调队列中，这样便可维护出最小值。
由于每个元素进队出队只有一次，所以综合时间复杂度为$O({n})$。
### 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') {
f = -1;
}
c = getchar();
}
while(c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
return x * f;
}
const int Maxn = 1 * 1e6 + 1;
int n, k, l, r, a[Maxn], q[Maxn];
int main() {
n = read(), k = read();
for(register int i = 1; i <= n; ++i) {
a[i] = read();
}
l = 1, r = 0;
for(register int i = 1; i <= n; ++i) { //最小值
while(l <= r && a[q[r]] >= a[i]) {
--r;
}
q[++r] = i;
while(q[l] + k - 1 < i) {
++l;
}
if(i >= k) {
printf("%d ", a[q[l]]);
}
}
puts("");
l = 1, r = 0;
for(register int i = 1; i <= n; ++i) { //最大值
while(l <= r && a[q[r]] <= a[i]) {
--r;
}
q[++r] = i;
while(q[l] + k - 1 < i) {
++l;
}
if(i >= k) {
printf("%d ", a[q[l]]);
}
}
puts("");
return 0;
}
```
------------
## 如何应用？
[POJ1821 Fence](http://poj.org/problem?id=1821)
### 题意：
现在有连续 $n(1≤n≤16,000)$ 块木板，编号为 $1$ — $n$ ， $k(1≤k≤100)$ 个粉刷匠，每个粉刷匠只能刷一次。第 $i$ 个人有两种选择：一是不刷，二是必须完成长度不超过 $L_i$ $(1≤L_i≤n)$ 并且包含 $S_i$ $(1≤S_i≤n)$ 的连续的木板。每完成一个任务第 $i$ 个人需要获得 $P_i$ 的 $(1≤P_i≤10,000)$ 的报酬，不同人的 $S_i$ 是不相同的。 求如何安排能够使得所有粉刷匠的报酬总和最大？
### 分析：
我们可以定义 $f[i][j]$ 代表前 $i$ 个粉刷匠粉刷完成至多前 $j$ 个木板的最大利益。
经观察，得状态转移有一下三种：
1. 不需要第 $i$ 个粉刷匠，即前 $i-1$ 个粉刷匠完成前 $j$ 个木板的工作：$f[i][j]=f[i-1][j]$
2. 不需要粉刷第 $j$ 块木板，即前 $i$ 个粉刷匠完成前 $j-1$ 个木板的工作：$f[i][j]=f[i][j-1]$
3. 前 $i-1$ 个粉刷匠粉刷到了第 $k$ 块木板，然后第 $i$ 个粉刷匠从第 $k+1$ 开始一直粉刷到第 $j$ 个木板。
$f[i][j]=Max(f[i][j],f[i-1][k]+p[i]×(j-k))$
前两种状态的决策点只有一个，时间复杂度为$O({n})$，没有必要优化。
而第三种情况，即第 $i$ 个粉刷匠要涂，我们可以假设我们是从 $k+1$ 涂到 $j$ 的，根据题意可以求出 $k$ 的取值范围，然后状态转移的条件限制了 $j$ 的取值范围。
我们考虑每次 $j$ 从小到大增加的过程，$j$ 对应的 $k$ 的取值是一个**上界不变下届递增的区间**，是一个滑动窗口，那我们可以用单调队列来**维护决策点** $k$ 的最优候选。
我们又可以发现，我们**在单调队列中，所维护的下标和权值均是单调的**。
### 代码：
```cpp
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') {
f = -1;
}
c = getchar();
}
while(c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
return x * f;
}
const int Maxn = 16061;
const int Maxk = 161;
int n, m, f[Maxk][Maxn], q[Maxn];
struct Node {
int l;
int p;
int s;
} a[Maxk];
inline bool Cmp(Node a, Node b) { // 计算单调队列要维护的值
return a.s < b.s;
}
inline int Calc(int i, int k) {
return f[i - 1][k] - a[i].p * k;
}
int main() {
n = read(), m = read(); // f[i][j]表示前i号工匠粉刷前j块木板的最大收入
for(register int i = 1; i <= m; ++i) {
a[i].l = read(), a[i].p = read(), a[i].s = read();
}
sort(a + 1, a + m + 1, Cmp);
for(register int i = 1; i <= m; ++i) { // 工匠
int l = 1, r = 0; // 初始化单调队列
for(register int k = max(0, a[i].s - a[i].l); k <= a[i].s - 1; ++k) { // 把可能的决策点插入deque
while(l <= r && Calc(i, q[r]) <= Calc(i, k)) { // 剔除队尾不合法的元素
r--;
}
q[++r] = k; // 当前状态k插入队尾
}
for(register int j = 1; j <= n; ++j) {
f[i][j] = max(f[i - 1][j], f[i][j - 1]); // i木匠不粉刷，或 j木板不粉刷
// 粉刷第k+1~j块木板时的转移
if(j >= a[i].s) { // j比s大粉刷才合法，必须包括s
while(l <= r && q[l] < j - a[i].l) { //队首 < 当前下标j - 粉刷距离L，不合法的决策点
l++;
}
if(l <= r) { // 队列非空时，利用队首转移
f[i][j] = max(f[i][j], Calc(i, q[l]) + a[i].p * j);
}
}
}
}
printf("%d\n", f[m][n]);
return 0;
}
```
------------
[LG4954 Tower of Hay G](https://www.luogu.com.cn/problem/P4954)
### 题意：
现在有 $n(1≤n≤16,000)$ 包干草，编号为 $1$ — $n$ ，每个干草堆的宽度为 $a_i$ ，先要按照严格的摆放（不能打乱顺序摆放，不能不摆）来建立一个高度为 $h$ 干草堆，干草堆要使上层干草的宽度不能超过下层的宽度。
求在所有可行的方案中，$h$ 的最大值。
### 分析：
首先，我们看到这道题，想到的第一个方法或许是**贪心**。
我们让高层尽可能的小，从后往前倒叙贪心。
但是我们可以举出个**反例**：
```
6
9 8 2 1 5 5
```
如果我们按照**倒叙读入**的思路，贪心出来的结果为 $5; 5; 1, 2, 8, 9$ 共三层。
但正确的结果却是 $5; 5, 1, 2; 8; 9$ 共四层。
可以得出，此贪心的错误之处在于前面的贪心使得**底层过大，难以扩展**。
然后，根据[抽屉原理](https://xyzl.blog.luogu.org/chou-ti-yuan-li)，我们可以得到一个较为贪心的结论。
构成最优解的所有方案中，一定有一种满足底层最小，即 **底层最小的方案一定可以构造出最高的层数**。
通俗点来说，就是干草堆底盘越小，塔身越瘦，就可以堆的越高。
此时，我们可以去考虑**动态规划**。
同贪心一样，我们将 $a$ 数组倒叙输入，求其**前缀和**。
我们可以定义两个数组来维护dp；
$f[i]$ 表示从塔尖到塔底且选到第 $i$ 堆草时，能够得到的最大高度；
$g[i]$ 表示高度为 $f[i]$ 时的草堆宽度。
得到转移方程为：$f[i]=f[j]+1$ ( $j$ 为满足 $j∈[0,i−1]$ 且 $g[j]≤sum[i]-sum[j]$ 的最后一个 $j$ )
因为我们要求最后一层的宽度尽可以能的小，所以得到 j 后有 $g[i]=sum[i]-sum[j]$。
这样我们转移的时间复杂度为 $O({n})$ ，总时间复杂度为 $O({n^2})$。
但数据范围不能支持我们如此朴素的dp，所以我们可以去考虑**单调队列优化**。
因为我们 $g$ 的状态转移方程为 $g[j]≤sum[i]-sum[j]$ ， 经过移项后得：$g[j]+sum[j]≤sum[i]$。
可以得出：若有 $k<j$ 且 $g[k]+s[k]⩾g[j]+s[j]$ ，则 $k$ 已经永远无法转移给他人，因为如果 $k$ 能够转移，那么 $j$ 也能够转移，而 $j$ 的位置要比 $k$ 更加靠后，这完全符合单调队列的性质。
所以我们可以维护以下这个值单调递增的队列：
```cpp
int Calc(int x) {
return sum[x] + g[x];
}
```
我们每次转移时，从队列中找到最后一个满足条件的位置 $j$ ，以单调队列中 $j$ 以左的元素从队首弹出。
然后从队尾再弹出 $g[j]+s[j]⩾g[i]+s[i]$，然后将位置 $i$ 入队。
综上，总时间复杂度为 $O({n})$。
### 代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') {
f = -1;
}
c = getchar();
}
while(c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
return x * f;
}
const int Maxn = 101101;
int n, a[Maxn], g[Maxn], q[Maxn], f[Maxn], sum[Maxn];
// f[i] 表示从塔尖到塔底且选到第i堆草时，能够得到的最大高度
// g[i] 表示高度为dp[i]时的草堆宽度
inline int Calc(register int x) {
return sum[x] + g[x];
}
// 干草堆越瘦，就能堆得越高
int main() {
n = read();
for(register int i = n; i >= 1; --i) { // 倒序输入干草堆的宽度
a[i] = read();
}
for(register int i = 1; i <= n; ++i) { // 前缀和
sum[i] = sum[i - 1] + a[i];
}
int l = 1, r = 0; // 初始化单调队列
for(register int i = 1; i <= n; ++i) {
// 维护满足sum[i] - sum[j] >= g[j]的最大的j(队首), 因为j越大， sum[i] - sum[j]越小
while(l <= r && sum[i] - sum[q[l]] >= g[q[l]]) {
++l;
}
//最后一个满足条件的位置 j-1
g[i] = sum[i] - sum[q[l - 1]];
f[i] = f[q[l - 1]] + 1; //状态转移
/*设当前候选决策点为j，那么须满足 g[j] + sum[j] <= sum[i]才能转移，
那么单调队列要维护g[x] + sum[x]的最小值, 因为这个值越小，sum[i]-sum[j]就越小，干草越窄
*/
while(l <= r && Calc(i) < Calc(q[r])) {
r--;
}
q[++r] = i;
}
printf("%d\n", f[n]);
return 0;
}
```
[LG5665 划分](https://www.luogu.com.cn/problem/P5665)
### 题意：
现在有长度为 $n(1≤n≤40,000,007)$ 的递增序列，要求划分使得**区间和平方**的和最小。
求对该数列的一个划分 $T = \{ k_1, k_2, \dots, k_p \}$，使得该划分满足 ：
$\sum\limits_{i=1}^{k_1} a_i\le \sum\limits_{i=k_1+1}^{k_2} a_i \le \dots \le \sum\limits_{i=k_p+1}^n a_i$，
且最小化
$ \left(\sum\limits_{i=1}^{k_1} a_i \right)^2+\left(\sum\limits_{i=k_1}^{k_2} a_i \right)^2+\cdots +\left(\sum\limits_{i=k_p+1}^n a_i \right)^2 $。
### 分析：
根据题意，可以得出我们所有分的段是**递增**的，我们可以 $f[i][j]$ 为为划分到第 $i$ 个的前驱是 $j$ ，即状态 $f[i][j]$ 表示对前 $i$ 个数字分段，上一段的结尾为 $j$ 的时候段平方和的最小值。
即 $f[i][j]$ $=$ $f[j][k]$ $+$ $($ $sum[i]$ $−$ $sum[j]$ $)$ $^2$
进行状态转移时，我们可以枚举出上一段的结尾 $j$，和再上一段的结尾 $k$ ，先判断是否满足转移条件，然后进行最小化转移，这样我们的时间复杂度就为为 $O({n^3})$。
但这样的时间复杂度是远远不够的，我们可以固定 $j$ ，可以发现在移动 $j$ 的过程中，$k$ 也在移动，满足一个单调性，然后我们维护一个 $f[i][j]$ 的最小值，此时我们的时间复杂度就为为 $O({n^2})$。
我们可以发现一个结论，在所有合法的情况中，都有 $f[i][j]$ $≤$ $f[i][j-1]$ 。
##### （本人太菜了，具体也不知道是怎么发现并严格证明的，但可以看一下[matthew99巨佬的博客](https://matthew99.blog.uoj.ac/blog/5299)）
所以我们可以使用一个单调队列，维护一个最右边的前驱，再结合前缀和的单调性，左端点满足条件移动，右端点维护单调递增，得到转移点时可以直接得到答案。
所以综合时间复杂度为$O({n})$。
### 代码：
以下给出非高精代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
inline long long read() {
long long x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') {
f = -1;
}
c = getchar();
}
while(c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
return x * f;
}
const int Maxn = 500005;
int n, tpye;
long long a[Maxn], sum[Maxn], q[Maxn], l[Maxn], w[Maxn];
unsigned long long f[Maxn];
inline long long Calc(register int x) { // 计算单调队列要维护的值
return sum[x] + w[x];
}
int main() {
n = read(), tpye = read();
if(!tpye) {
for(register int i = 1; i <= n; ++i) {
a[i] = read();
}
}
for(register int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + a[i];
}
int l = 1, r = 0; // 初始化单调队列
for(register int i = 1; i <= n; ++i) {
while(l <= r && sum[i] - sum[q[l]] >= w[q[l]]) {
++l;
}
w[i] = sum[i] - sum[q[l - 1]];
f[i] = f[q[l - 1]] + w[i] * w[i]; //状态转移
while(l <= r && Calc(i) <= Calc(q[r])) { // // 把可能的决策点插入调队列
r--;
}
q[++r] = i;
}
printf("%lld\n", f[n]);
return 0;
}
```
------------
## 总结：
单调队列的单调是指数组**下标**的单调及所维护的**权值**的单调。
一般情况下，碰到单调队列优化dp常有以下三种现象：
1. 状态转移方程一定是取**最值**。
2. $f[i] = Max/Min(f[j]+{A_i}+{B_i})$
3. 决策点有个**单调的上界或下界**
单调队列优化dp是一种常见的dp优化方式，是掌握和运用**斜率优化**的基础，很多动态规划题目都会运用到，所以追求卓越同学一定要掌握。