概述
单调队列就是通过排除求最值时候的冗余，从而是队列具有性质，可以方便求解问题。
DP的两个阶段：
- 朴素DP的基本原理——闫氏DP分析法
- 对朴素DP进行优化
闫氏DP分析法的拓展 ：在一个有限的集合中求最值。
单调队列练习
输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。
注意： 子序列的长度至少是 1。
输入格式
第一行输入两个整数 n,m。
第二行输入 n 个数，代表长度为 n 的整数序列。
同一行数之间用空格隔开。
输出格式
输出一个整数，代表该序列的最大子序和。
数据范围
1≤n,m≤300000
输入样例：
6 4
1 -3 5 1 -2 3
输出样例：
7
这道题目是使用暴力的思路想，然后优化。
首先，朴素的思路就是枚举每一个长度不大于m的区间，遍历求最大值。
这里涉及到区间的操作，所以转化为前缀和。
a[x] + ... + a[y] = sum[y] - sum[x - 1]
这时候，我们枚举右端点，sum[y]已经固定，sum[x]需要在滑动的区间内取得最小值，所以使用滑动窗口。
#include <bits/stdc++.h>
using namespace std;
#define N 300020
int n, m;
int s[N];// 前缀和
int q[N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", s+i);
s[i] += s[i - 1];
}
int res = -0x3f3f3f3f;// 由于序列的长度可以为 0
int hh = 0, tt = -1;
q[++tt] = 0;// 由于是前缀和，所以应该 包含0
for(int i = 1; i <= n; i++)
{
while(hh <= tt && q[hh] < i - m) hh ++;
if(hh <= tt)
res = max(s[i] - s[q[hh]], res);
while(hh <= tt && s[q[tt]] >= s[i]) tt --;
q[++tt] = i;
}
printf("%d", res);
return 0;
}
John 打算驾驶一辆汽车周游一个环形公路。
公路上总共有 n 个车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。
John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。
在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。
任务：判断以每个车站为起点能否按条件成功周游一周。
输入格式
第一行是一个整数 n，表示环形公路上的车站数；
接下来 n 行，每行两个整数 pi,di，分别表示表示第 i 号车站的存油量和第 i 号车站到 顺时针方向 下一站的距离。
输出格式
输出共 n 行，如果从第 i 号车站出发，一直按顺时针（或逆时针）方向行驶，能够成功周游一圈，则在第 i 行输出 TAK，否则输出 NIE。
数据范围
3≤n≤1e6
0≤pi≤2×1e9
0≤di≤2×1e9
输入样例：
5
3 1
1 2
5 2
0 1
5 4
输出样例：
TAK
NIE
TAK
NIE
TAK
分析
- 由于要求解顺时针或者是逆时针，这两种情况具有对称性，所以先考虑一种。
- 是一个环，直接求的话不能利用之前已经求解好的状态，所以需要破环成链。
- 可以把
p[i]和d[i]做一个差值。满足要求的情况就是从 i 号点到 i + 1 号点的所有前缀全部是大于0的。
- 求解以某一点为结尾的所有不超过n的前缀中的最值问题，就可以使用上一题的思路。
真可谓思路不难，调BUG离谱
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000020
ll p[N], d[N], a[N*2];// a表示前缀
int n;
int q[N*2];
bool ans[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++){
scanf("%lld%lld", p + i, d + i);
}
// 顺时针情况************************************
for(int i = 1; i <= n; i++){
a[i] = p[i] - d[i];
a[i + n] = p[i] - d[i];
}
for(int i = 1; i <= 2 * n; i++){
a[i] = a[i] + a[i - 1];
}
int tt = -1, hh = 0;
for(int i = n * 2; i >= 0; i--)
{
while(hh <= tt && q[hh] > i + n) hh ++;
if(hh <= tt && i < n) {
if(a[i]<=a[q[hh]]) ans[i+1] = true;
// a[i]<=a[q[hh]]表示的是i + 1 到 q[hh]的区间之和大于等于0
}
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
}
// 逆时针情况************************************
d[0] = d[n];
for(int i = 1; i <= n; i++){
a[i + n] = a[i] = p[i] - d[i - 1];
}
a[0] = 0;
for(int i = 1; i <= 2 * n; i++){
a[i] = a[i] + a[i - 1];
}
tt = -1, hh = 0;
q[++tt] = 0;
for(int i = 1; i <= n * 2; i++)
{
while(hh <= tt && q[hh] < i - n) hh ++;
if(hh <= tt && i > n) {
if(a[q[hh]] <= a[i]) ans[i - n] = true;
// a[i]<=a[q[hh]]表示的是q[hh]+1到i的区间之和大于等于0
}
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
}
for(int i = 1; i <= n; i++){
if(ans[i]){
puts("TAK");
}else{
puts("NIE");
}
}
return 0;
}
二维单调队列问题
有一个 a×b 的整数组成的矩阵，现请你从中找出一个 n×n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
输入格式
第一行为三个整数，分别表示 a,b,n 的值；
第二行至第 a+1 行每行为 b 个非负整数，表示矩阵中相应位置上的数。
输出格式
输出仅一个整数，为 a×b 矩阵中所有“n×n 正方形区域中的最大整数和最小整数的差值”的最小值。
数据范围
2≤a,b≤1000,
n≤a,n≤b,n≤100,
矩阵中的所有数都不超过 1e9。
输入样例：
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
输出样例：
1
这一道题目算是一个典型的二维的滑动窗口问题。
如果直接滑动，那么会比较复杂。所以我们先按照行来，存储row_max[i][j]为以[i][j]结尾的，每行的最值。
然后对于row_max[i][j]再纵着来一下就可以了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1020;
int w[N][N];
int row_max[N][N];
int row_min[N][N];
int n, m, K;
int q[N];
void getmax(int *a, int *b, int tot)
{
int tt = -1, hh = 0;
for(int i = 1; i <= tot; i++){
while(hh <= tt && q[hh] <= i - K) hh++;
while(hh <= tt && a[q[tt]] <= a[i]) tt--;// BUG1: a[q[tt]] <= a[i]写反了
q[++tt] = i;
if(hh <= tt) b[i] = a[q[hh]];
}
}
void getmin(int *a, int *b, int tot)
{
int tt = -1, hh = 0;
for(int i = 1; i <= tot; i++){
while(hh <= tt && q[hh] <= i - K) hh++;
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
if(hh <= tt) b[i] = a[q[hh]];
}
}
int main()
{
scanf("%d%d%d", &n, &m, &K);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
scanf("%d", &w[i][j]);
}
for(int i = 1; i <= n; i++){
getmax(w[i], row_max[i], m);
getmin(w[i], row_min[i], m);
// BUG3：getmin(w[i], row_max[i], m);
}
static int a[N], b[N], c[N];
int res = 0x7f7f7f7f;
for(int i = K; i <= m; i++)
{
for(int j = 1; j <= n; j++) a[j] = row_max[j][i];// BUG 2:要从1开始（虽然K之前不参与更新res，但是参与求最值）
getmax(a, b, n);
for(int j = 1; j <= n; j++) a[j] = row_min[j][i];
getmin(a, c, n);
for(int i = K; i <= n; i++) res = min(res, b[i] - c[i]);
}
printf("%d\n", res);
return 0;
}
使用单调队列来优化DP
烽火台是重要的军事防御设施，一般建在交通要道或险要处。
一旦有军情发生，则白天用浓烟，晚上有火光传递军情。
在某两个城市之间有 n 座烽火台，每个烽火台发出信号都有一定的代价。
为了使情报准确传递，在连续 m 个烽火台中至少要有一个发出信号。
现在输入 n,m 和每个烽火台的代价，请计算在两城市之间准确传递情报所需花费的总代价最少为多少。
输入格式
第一行是两个整数 n,m，具体含义见题目描述；
第二行 n 个整数表示每个烽火台的代价 ai。
输出格式
输出仅一个整数，表示最小代价。
数据范围
1≤m≤n≤2e5
0≤ai≤1000
输入样例：
5 3
1 2 5 6 2
输出样例：
4
这一道题目可能会想到状态机，但是使用状态机的话就必须有m个状态，并不切合实际。
设状态：f[i]表示从第一个到第 i 个，并且第 i 个被点燃的情况下的最小花费。
我们把n+1的代价视为0，点燃n + 1视为DP结束。
对于当前的，选择dp[i - m], dp[i - m + 1] ..... d[i -1]中的最小的，这满足滑动窗口
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int n, m;
int dp[N];
int q[N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", a+i);
int hh = 0, tt = -1;
q[++tt] = 0;
for(int i = 1; i <= n + 1; i ++){
while(hh <= tt && q[hh] < i - m) hh ++;
if(hh <= tt) dp[i]= dp[q[hh]] + a[i];
while(hh <= tt && dp[q[tt]] >= dp[i]) tt --;
q[++tt] = i;// 注意：队列里面存放的一直都是下标
}
printf("%d\n", dp[n + 1]);
//for(int i = 1; i <= n+1; i++) cout << dp[i] << " ";
return 0;
}
高二数学《绿色通道》总共有 n 道题目要抄，编号 1,2,…,n，抄第 i 题要花 ai 分钟。
小 Y 决定只用不超过 t 分钟抄这个，因此必然有空着的题。
每道题要么不写，要么抄完，不能写一半。
下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。
这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。
现在，小 Y 想知道他在这 t 分钟内写哪些题，才能够尽量减轻马老师的怒火。
由于小 Y 很聪明，你只要告诉他最长的空题段至少有多长就可以了，不需输出方案。
输入格式
第一行为两个整数 n,t。
第二行为 n个整数，依次为 a1,a2,…,an
输出格式
输出一个整数，表示最长的空题段至少有多长。
数据范围
0<n≤5e4
0<ai≤3000
0<t≤1e8
输入样例：
17 11
6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5
输出样例：
3
题解
这一道题目在具体做决定的时候，会发现并不知道最终答案，导致过程中无法把握舍与得。
这时候我们可以想到使用二分答案。
容易得知，显然具有单调性。
二分之后，就是相当于判断相邻两个最远的距离是mid，求出抄完的时间满不满足。
（大致思路和上一道题目类似）
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 20;
int a[N];
int T, n;
int f[N], q[N];
bool ck(int mid)
{
int hh = 0, tt = -1;
q[++tt] = 0;
for(int i = 1; i <= n + 1; i++){
while(hh <= tt && q[hh] < i - mid - 1) hh ++;
if(hh <= tt) f[i] = f[q[hh]] + a[i];
while(hh <= tt && f[q[tt]]>= f[i]) tt --;
q[++tt] = i;
}
//cout << mid << " " << f[n + 1] << "\n";
if(f[n + 1] <= T) return true;
else return false;
}
int main()
{
scanf("%d%d", &n, &T);
for(int i = 1; i <= n; i++) scanf("%d", a + i);
int l = 0, r = n;
while(l < r){
int mid = (l + r) >> 1;
if(ck(mid)) r = mid;
else l = mid + 1;
}
printf("%d", l);
return 0;
}
在一年前赢得了小镇的最佳草坪比赛后，FJ 变得很懒，再也没有修剪过草坪。
现在，新一轮的最佳草坪比赛又开始了，FJ 希望能够再次夺冠。
然而，FJ 的草坪非常脏乱，因此，FJ 只能够让他的奶牛来完成这项工作。
FJ 有 N 只排成一排的奶牛，编号为 1 到 N。
每只奶牛的效率是不同的，奶牛 i 的效率为 Ei。
编号相邻的奶牛们很熟悉，如果 FJ 安排超过 K 只编号连续的奶牛，那么这些奶牛就会罢工去开派对。
因此，现在 FJ 需要你的帮助，找到最合理的安排方案并计算 FJ 可以得到的最大效率。
注意，方案需满足不能包含超过 K 只编号连续的奶牛。
输入格式
第一行：空格隔开的两个整数 N 和 K；
第二到 N+1行：第 i+1 行有一个整数 Ei。
输出格式
共一行，包含一个数值，表示 FJ 可以得到的最大的效率值。
数据范围
1≤N≤1e5
0≤Ei≤1e9
输入样例：
5 2
1
2
3
4
5
输出样例：
12
样例解释
FJ 有 5 只奶牛，效率分别为 1、2、3、4、5。
FJ 希望选取的奶牛效率总和最大，但是他不能选取超过 2 只连续的奶牛。
因此可以选择第三只以外的其他奶牛，总的效率为 1 + 2 + 4 + 5 = 12。
题解一
其实从上面两道题目中可以看出来：
对于区间中连续的m个中，必须选择一个
这种情况，可以使用单调队列进行优化。
所以，在这里可以反过来思考，这样就转化为了上面的思路。
f[i]表示不选择第 i 个数字，在前 i 个数字中不选择的数字加起来的最小值。
在任意一个连续的区间内，需要满足在 K+1 的范围内至少有一个不选择。
最后使用总的和减去上述求出的结果就行。
题解二-y总思路
状态表示：f[i]表示从前 i 个奶牛中选择，并且满足没有连续选择超过 K 头奶牛的所有情况。
属性：最大值。
转移：
- 不选择第 i 头奶牛，那么
f[i] = f[i - 1]
- 选择第 i 头奶牛
这时候应该注意不能让连续的大于K
对于第二种情况：
枚举x
(
1
≤
x
≤
K
)
(1\le x\le K)
(1≤x≤K)，表示选择了包括 i 在内的从后往前数的连续 x 个奶牛，第
i
−
x
i - x
i−x头奶牛不选的所有情况中的最大值。
由于涉及到区间问题，转化为前缀和。
有状态转移公式：f[i] = s[i] - s[i - x] + f[i - x - 1]
(
1
≤
x
≤
K
)
(1\le x\le K)
(1≤x≤K)
为了方便表示，令
g
(
x
)
=
f
[
x
−
1
]
−
s
[
x
]
g(x) = f[x - 1] - s[x]
g(x)=f[x−1]−s[x]
边界情况：
g
(
0
)
g(0)
g(0)：这种情况表示的是从 1 到 i 全部选择的情况。应该为0.
g
(
1
)
g(1)
g(1)：f[0]为0，表示不选择任何奶牛的最大值。
#include <bits/stdc++.h>
using namespace std;
int n, K;
const int N = 1e5 + 20;
typedef long long ll;
ll s[N];
ll f[N];
ll q[N];
inline ll g(ll x){
if(!x) return 0;
return f[x - 1] - s[x];
}
int main()
{
scanf("%d%d", &n, &K);
for(int i = 1; i <= n; i++){
scanf("%lld", s + i);
s[i] += s[i - 1];
}
int hh = 0, tt = -1;
q[++tt] = 0;
for(int i = 1; i <= n; i++)
{
while(hh <= tt && q[hh] < i - K) hh ++;
if(hh <= tt) f[i] = max(f[i - 1], s[i] + g(q[hh]));
// BUG 记录：只顾着写单调队列优化了，忘了还有不选择这种情况
while(hh <= tt && g(q[tt]) <= g(i)) tt--;
q[++tt] = i;
}
printf("%lld", f[n]);
return 0;
}
