时间复杂度=状态数量 * 计算每个状态所需时间
背包问题
空间优化至一维时需要考虑循环顺序，朴素的二维写法则不需要
01 背包
求价值 max
01背包问题：有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
状态转移方程：$f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])$
1）朴素二维 DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include<iostream>
using namespace std;
const int N = 1005;
int f[N][N]; // f[i][j] 前i个物品，容积 <= j 时的最大价值
int v[N], w[N]; // 体积 价值
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (v[i] <= j) { // 可选第i个物品，比较最大值
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
} else { // 不选第i个物品
f[i][j] = f[i - 1][j];
}
}
}
cout << f[n][m];
return 0;
}
|
2）空间优化至一维（逆向遍历）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include<iostream>
using namespace std;
const int N = 1005;
int f[N]; // f[j] 容积 <= j 时的最大价值
int v[N], w[N]; // 体积 价值
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= n; i++) {
// 反向遍历，f[j - v] 和 f[j] 便是 i - 1 层
for (int j = m; j >= 1; j--) {
if (v[i] <= j) { // 可选第i个物品，比较最大值
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
}
cout << f[m];
return 0;
}
|
求方案数量
278. 数字组合：给定 $N$ 个正整数 $A_1,A_2,…,A_N$，从中选出若干个数，使它们的和为 $M$，求有多少种选择方案
状态转移方程：$f[i][j] = f[i - 1][j] + f[i - 1][j - v[i]]$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include<iostream>
using namespace std;
const int M = 10005, N = 105;
int f[N][M]; // f[i][j] 前 i 个数中选择的和恰好等于 j 的数量
int v[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i];
// 从前i个物品中选，且价值为0的方案数均为1
// 什么都不选就是一种选法
for(int i = 0; i < n; i++) f[i][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j >= v[i]) f[i][j] = f[i - 1][j] + f[i - 1][j - v[i]];
else f[i][j] = f[i - 1][j];
}
}
cout << f[n][m];
return 0;
}
|
空间优化（逆向遍历）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<iostream>
using namespace std;
const int M = 10005, N = 105;
int f[M]; // f[j] 和恰好等于 j 的数量
int v[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i];
// 初始化 f[0] = 1, f[1~m] = 0
f[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
f[j] = f[j] + f[j - v[i]];
}
}
cout << f[m];
return 0;
}
|
完全背包
求价值 max
完全背包问题：每种物品都有无限件可用
完全背包：$f[i][j] = max(f[i - 1][j], f[ i ][j - v[i]] + w[i])$
对比 0-1背包：$f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include<iostream>
using namespace std;
const int N = 1005;
int f[N][N]; // f[i][j] 前i个物品，容积 <= j 时的最大价值
int v[N], w[N]; // 体积 价值
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (v[i] <= j) {
f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
} else {
f[i][j] = f[i - 1][j];
}
}
}
cout << f[n][m];
return 0;
}
|
空间优化（正向遍历）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<iostream>
using namespace std;
const int N = 1005;
int f[N]; // f[j] 容积 <= j 时的最大价值
int v[N], w[N]; // 体积 价值
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= n; i++) {
// 正向遍历
for (int j = v[i]; j <= m; j++) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m];
return 0;
}
|
求方案数量
1021. 货币系统：给你一个 n 种面值的货币系统，求组成面值为 m 的货币有多少种方案。
状态转移方程：$f[i][j] = f[i - 1][j] + f[i][j - v[i]]$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include<iostream>
using namespace std;
const int M = 3005, N = 20;
long long f[N][M]; // f[i][j] 前 i 个数中选择的和恰好等于 j 的数量
int v[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i];
// 从前i个物品中选，且价值为0的方案数均为1
// 什么都不选就是一种选法
for(int i = 0; i <= n; i++) f[i][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j >= v[i]) f[i][j] = f[i - 1][j] + f[i][j - v[i]];
else f[i][j] = f[i - 1][j];
}
}
cout << f[n][m];
return 0;
}
|
空间优化（正向遍历）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<iostream>
using namespace std;
const int M = 3005, N = 20;
long long f[M]; // f[j] 前 i 个数中选择的和恰好等于 j 的数量
int v[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i];
// 价值为0的方案数均为1，什么都不选就是一种选法
f[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) {
f[j] = f[j] + f[j - v[i]];
}
}
cout << f[m];
return 0;
}
|
线性 DP
数字三角形
898. 数字三角形：给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
1
2
3
4
5
|
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <iostream>
using namespace std;
const int N = 510;
int w[N][N];
int f[N][N]; // f[i][j] 从 (i, j) 走到底层的最大值
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> w[i][j];
}
}
// 初始化最后一层
for (int i = 1; i <= n; i++) f[n][i] = w[n][i];
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + w[i][j];
}
}
cout << f[1][1];
return 0;
}
|
简化版（不需要存储原始数据）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
using namespace std;
const int N = 510;
int f[N][N]; // f[i][j] 从 (i, j) 走到底层的最大值
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> f[i][j];
}
}
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
}
}
cout << f[1][1];
return 0;
}
|
1015. 摘花生：Hello Kitty 想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走，不能向西或向北走。问Hello Kitty最多能够摘到多少颗花生。
注意：初始化全为 0，遍历从下标 1 开始
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <iostream>
using namespace std;
const int N = 110;
// int w[N][N];
int f[N][N]; // f[i][j] 从 (i, j) 走到东南角的最大值
int main() {
int T, n, m;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// cin >> w[i][j];
cin >> f[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// f[i][j] = max(f[i][j - 1], f[i - 1][j]) + w[i][j];
f[i][j] += max(f[i][j - 1], f[i - 1][j]);
}
}
cout << f[n][m] << endl;
}
return 0;
}
|
1018. 最低通行费：
一个商人穿过一个 $N×N$ 的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。
每穿越中间 1 个小方格，都要花费 1 个单位时间。商人必须在 $(2N−1)$ 个单位时间穿越出去。
而在经过中间的每个小方格时，都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去，请问至少需要多少费用？
注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。
最长 2N - 1 即不能有回头路，求最小值注意初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include <iostream>
using namespace std;
const int N = 110, inf = 1e9;
int w[N][N];
int f[N][N]; // f[i][j] 从 (i, j) 走到东南角的最大值
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> w[i][j];
}
}
// 初始化
for (int i = 1; i <= n; i++) {
f[i][0] = f[0][i] = inf;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// 特判起始点 f[1][1] = w[1][1]
if (i == 1 && j == 1) {
f[i][j] = w[i][j];
} else {
f[i][j] = min(f[i][j - 1], f[i - 1][j]) + w[i][j];
}
}
}
cout << f[n][n] << endl;
return 0;
}
|
写法二：初始化写进主循环，在主循环中对第一行/第一列特殊判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <iostream>
using namespace std;
const int N = 110, inf = 1e9;
int w[N][N];
int f[N][N]; // f[i][j] 从 (i, j) 走到东南角的最大值
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> w[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// 特判起始点 f[1][1] = w[1][1]
if (i == 1 && j == 1) {
f[i][j] = w[i][j];
} else {
f[i][j] = inf;
if (i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);
if (j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);
}
}
}
cout << f[n][n] << endl;
return 0;
}
|
1027. 方格取数 (走两次)：
设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：
某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。
在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。
从 A 点到 B 点共走了两次，所以我们可以设两条路径是同时出发的，所以两条路径时很容易想到维护当前两条路径的状态（坐标）也就是 $f[x1][y1][x2][y2]$
同时出发则有：$x1+y1=x2+y2=k, y1 = k - x1, y2 = k - x2$，状态可优化成 $f[k][x1][x2]$。参照数字三角形模型，4 个状态转移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <iostream>
using namespace std;
const int N = 15;
int w[N][N];
int f[N*2][N][N]; // f[k][x1][x2]: (x1, k - x1), (x2, k - x2)
int main() {
int n;
cin >> n;
int r, c, x;
while (cin >> r >> c >> x, r || c || x) {
w[r][c] = x;
}
// (1, 1) -> (n, n)
for (int k = 2; k <= n + n; k++) {
for (int x1 = 1; x1 <= n; x1++) {
for (int x2 = 1; x2 <= n; x2++) {
int y1 = k - x1, y2 = k - x2;
if (y1 >= 1 && y1 <= n && y2 >= 1 && y2 <= n) {
int t = w[x1][y1];
// 判断是否重复 没重复则可以添加
if (x1 != x2) t += w[x2][y2];
int &x = f[k][x1][x2];
x = max(x, f[k - 1][x1 - 1][x2] + t); // x1-1, y2-1
x = max(x, f[k - 1][x1][x2 - 1] + t); // y1-1, x2-1
x = max(x, f[k - 1][x1 - 1][x2 - 1] + t); // x1-1, x2-1
x = max(x, f[k - 1][x1][x2] + t); // y1-1, y2-1
}
}
}
}
cout << f[n * 2][n][n];
return 0;
}
|
275. 传纸条 (上一题的另一种写法，思路一致)：
一次素质拓展活动中，班上同学安排坐成一个 m 行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，他们可以通过传纸条来进行交流。
纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 (1,1)，小轩坐在矩阵的右下角，坐标 (m,n)。
从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。
在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。
班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙，反之亦然。
全班每个同学愿意帮忙的好感度有高有低（小渊和小轩的好心程度没有定义，输入时用 0 表示），可以用一个 0∼100 的自然数来表示，数越大表示越好心。
小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。
现在，请你帮助小渊和小轩找到这样的两条路径。
点的范围 $1 <= i <= n, 1 <= k - i <= m (k - m <= i <= k - 1)$
⇒ $max(1, k - m) <= i <= min(n, k - 1)$
除起点终点外，每点都有 > 0 的值，最后的结果不会选择有重复点的方案，可知每步的最大方案都不会有重复的点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <iostream>
using namespace std;
const int N = 55;
int w[N][N];
int f[N*2][N][N]; // f[k][x1][x2]: (x1, k - x1), (x2, k - x2)
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> w[i][j];
}
}
// (1, 1) -> (n, n)
for (int k = 2; k <= n + m; k++) {
for (int x1 = max(1, k - m); x1 <= min(n, k - 1); x1++) {
for (int x2 = max(1, k - m); x2 <= min(n, k - 1); x2++) {
int y1 = k - x1, y2 = k - x2;
int t = w[x1][y1];
// 判断是否重复 没重复则可以添加
if (x1 != x2) t += w[x2][y2];
// 4 个状态
for (int a = 0; a <= 1; a++) {
for (int b = 0; b <= 1; b++) {
f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1 - a][x2 - b] + t);
}
}
}
}
}
cout << f[n + m][n][n]; // (n, m), (n, m)
return 0;
}
|
最长上升子序列 LIS
895. 最长上升子序列：常规 DP 复杂度 $O(n^2)$，贪心+二分复杂度 ${O(nlogn)}$，详见 LeetCode-300. 最长递增子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
using namespace std;
const int N = 1010;
int a[N], f[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
// 初始化为 1
for (int i = 0; i < n; i++) f[i] = 1;
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
}
res = max(res, f[i]);
}
cout << res;
return 0;
}
|
最长公共子序列 LCS
897. 最长公共子序列：$O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N];
int main() {
int n, m;
cin >> n >> m;
cin >> a + 1 >> b + 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 子序列不要求连续
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j]) {
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
}
}
cout << f[n][m];
return 0;
}
|
LIS + LCS
最短编辑距离
902. 最短编辑距离 | 899. 编辑距离：$O(n^2)$
当 $a[i] == b[j]$，$f[i][j] = f[i - 1][j - 1];$
当 $a[i] != b[j]$，$f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1;$
从 a 变为 b 的角度看，$f[i - 1][j - 1]$ 是替换（$a[i]$ 替换为 $b[j]$），$f[i - 1][j]$ 是删除（删除 $a[i]$），$f[i][j - 1]$ 是插入（在 $a[i]$ 后插入 $b[j]$）。
注意初始化，$dp[i][0] = i; dp[0][j] = j;$ 可以表示为 $dp[i][0] = dp[i-1][0] + 1;$ 相邻变化次数多1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include <iostream>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N];
int main() {
int n, m;
cin >> n >> a + 1 >> m >> b + 1;
// 初始化
for (int i = 0; i <= n; i++) f[i][0] = i;
for (int i = 0; i <= m; i++) f[0][i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1];
else f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
}
}
cout << f[n][m];
return 0;
}
|
状态转移的其他写法
1
2
3
4
5
6
|
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
if (a[i] == b[j]) {
f[i][j] = min(f[i][j], f[i - 1][j - 1]);
} else {
f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
|
1
2
|
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1; // 相等也可以插入 删除
f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j])); // 替换
|
状态机 DP
状态压缩DP
计数 DP
区间 DP
树形 DP
记忆化搜索
901. 滑雪
给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
1
2
3
4
5
6
7
8
9
|
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
|
- 在给定矩阵中，一条可行的滑行轨迹为 24−17−2−1。
- 在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−1，沿途共经过 25 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310;
int h[N][N];
int f[N][N]; // 记忆化搜索
int n, m;
int xx[4] = {-1, 0, 1, 0}, yy[4] = {0, 1, 0, -1};
int dp(int x, int y) {
int &v = f[x][y];
if (v != -1) return v;
v = 1; // 自己一个点路径长为1
for (int i = 0; i < 4; i++) {
int a = x + xx[i], b = y + yy[i];
if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] > h[x][y]) {
v = max(v, dp(a, b) + 1);
}
}
return v;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n ;i++) {
for (int j = 1; j <= m; j++) {
cin >> h[i][j];
}
}
memset(f, -1, sizeof f);
int res = 0;
for (int i = 1; i <= n ;i++) {
for (int j = 1; j <= m; j++) {
res = max(res, dp(i, j));
}
}
cout << res;
return 0;
}
|
练习题：321. 棋盘分割
单调队列优化
Alfly
