单调栈
概念：引入单调栈
请先阅读相关知识：单调队列
同样的，单调栈是一个为了维护单调性弹出元素的栈，他从栈顶到栈底是单调的。
模拟：了解单调栈其实和本质单调队列一样。单调栈可以在时间复杂度为 $O(n)$ 的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。
下面我们以数组 [4, 3, 2, 5, 7, 4, 6, 8] 为例，模拟一下「单调递减栈」的进栈、出栈过程。具体过程如下：
以数组 $[4, 3, 2, 5, 7, 4, 6, 8]$ 为例，遍历顺序为从左到右。
步骤
待插入元素
操作
结果（左侧为栈底）
作用
1
4
4 入栈
$ [4] $
元素 4 的左侧无比 4 小的元素
2
3
4 出栈，3 入栈
$[3]$
元素 3 的左侧无比 3 小的元素
3
2
3 出栈，2 入栈
$[2]$
元素 2 的左侧无比 2 小的元素
4
5
5 入栈
$[2, 5]$
元素 5 的左侧第一个比 5 小的元素是：2
5
7
7 入栈
$[2, 5, 7]$
元素 7 的左侧第一个比 7 小的元素是：5
6
4
7 出栈，5 出栈，4 入栈
...
单调队列
概念：什么是单调队列单调队列，顾名思义就是单调的队列，那有些人就说了 “那你这单调队列和 priority_queue 有什么区别” 区别可大了，首先 priority_queue 是一个堆，其次，单调队列维护单调性的方式可不是把里面的东西排序，而是直接弹出元素。
单调队列的好处就是可以在 $O(n)$ 的时间内知道一个数组所有长度为一个固定值的子区间中的极值。
模拟：单调队列如何维护单调性假设现在我们有一个序列：
A = \{ 1,3,-1,-3,5,3,6,7 \}我们要求他所有长度为 $3$ 的子区间中的最大值，现在我们就假设我们只有一个队列，看看如何得出我们要的答案
123456789101112131415161718192021222324252627282930/*初始值：Q = empty插入 1 ，队列：Q = {1}插入 3 ，由于我们的队首需要是答案，所以把1弹出：Q = {3}插入 -1，-1 < 3 符合队列头部是答案的需求，不用动Q = {3, -1}插入 -3，由于 3 已经超出了规定子区 ...
CF11D - A Simple Task
题面题目链接大秦 为你打开 题目传送门
题目翻译给定一个简单无向图，求里面简单环的个数。
注：简单环是顶点和边不重复的环。
思路一样的，用状态标注经过的点，记录最后一个点，然后更新，如果绕绕绕绕回了走过的点，那就有环。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include<bits/stdc++.h>using namespace std;int n, m;int mp[20][20];long long dp[1 << 20][20];void Input() { scanf("%d%d", &n, &m); int u, v; for (int i = 1; i <= m; i++) { scanf("%d%d", &u, &v); ...
517七段第六课C
题面题目链接大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
有一个矩形状的迷宫，它被分为 $n \times m$ 个位置。有序对（行号，列号）表示迷宫中的位置，行号从 $1$ 到 $n$ 编号，列号从 $1$ 到 $m$ 编号。
从当前位置移动到下一个位置花费一步，而且只有同时满足以下条件才能移动到下一个位置：
1、下一个位置与当前位置相邻（上下或左右，4个方向）；
2、开着的门是可以通行的，但锁着的门不是；
3、不能通过一堵墙。
游戏开始时，所有的门是锁着的，一种类型的钥匙只能打开对应类型的门。只有在拿到对应钥匙之后才能打开相应的门。
经过某格子时，即可获得该格子所有钥匙。
请计算一下从 $(1,1)$ 到 $(n,m)$ 最少要花费几步。
思路典型的走迷宫 BFS 题。但是这次他有门和钥匙，那我们状压的东西也很明显了，就是我们身上有几把钥匙，这样就可以解决门的问题了，其他基本就是最最简单的 BFS 。详见代码。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243 ...
HDU5691 Sitting in Line
题面大秦 为你打开 题目传送门
思路这道题说数字分两种，固定的和非固定的，让你给非固定的排列，让相邻数字的乘积和最大。
同样数据范围很小，$n$ 只有 $16$ ，显然还是状压 DP，状态同样是排好了什么什么数字，最后一个排好的数字是什么。因为我们默认是把要排的数字一位一位排下来，这样就更方便递推。
这道题相对简单，初始化要分情况：
第一个固定，只有固定的数字是第一
第一个不固定，谁都可以是第一个
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include<bits/stdc++.h>using namespace std;int n;int a[20], p[20];int b[20];int dp[1 << 20][20];void Input() { scanf("%d", &n); ...
POJ3311 Hie with the Pie
题面大秦 为你打开 题目传送门
题目翻译：有 $n$ 个地方（标号 $1$ 到 $n$ ）要从标号为 $0$ 的地方出去，经过所有的地方之后回来，求最短的时间，输入 $(n+1)$ 的矩阵 $a$，$a[i][j]$表示顶点 $i$ 到顶点 $j$ 所需要的时间。
第一行输入一个整数 $n(1≤n≤10)$ 。
接下来 $𝑛+1$ 行，每行 $n+1$ 个整数，表示矩阵中的元素，矩阵中的元素在区间 $[1,1000]$ 内。
思路这道题我们要同时兼顾经过了哪些点（因为要经过所有点），所以最好的方式就是把经过的点存下来，但是想要在递推过程中记录这些东西，有点困难。发现数据范围只有 $10$ 不难想到状压DP。因为状压DP是基于集合的DP，每经过一个点，就在状态中标记。
另外要处理某两个点之间的最短路，因为只有 $10$ 的数据范围，所以这个可以用 floyd 水水过。
此外，在标记每一个点的是否经过，还有一个很重要的元素是最后一个点是哪里。就比如说：
121 4 3 2 1 2 3 4
同样是经过了点 1 2 3 4 但是顺序不一样，路程就可能有变化，另外我们要从最后一个经过的点往 ...
状压DP
概念：引入状压在我们做题的过程中，有很多选或不选的题目，因为递归不好优化代码也长，我们可以使用状态压缩来解决这个问题。
状压状压，是状态压缩的缩写，向上面举的例子，状态就是选或不选，想要把 $n$ 个物品的状态压缩。能想到的就是二进制吧，我们把第 $i$ 个物品的状态放在第 $i$ 位。当然，状压可以不是二进制状态。
运用：熟悉状压比如，我现在要枚举什么什么数量最大的组合，那么使用状压可以写出如下代码。
123456789for(int i = 0; i < (1 << n); i++) { int tot = 0; for(int j = 0; j < n; j++) { if((1 << j) & i) { tot += a[j]; } } ans = max(ans, tot);}
复杂度 $O(n\times2^n)$ 这就是状压的最基本运用。
拓展：状态压缩DP某一些 DP 的数据范围比较小，大概是 ...
517七段第五课I
题面大秦 为你打开 题目传送门
看不了的就看下面罢
从一个 $n\times n$ 的矩阵中选出一个元素之和最大的非空子矩阵。
思路思考一下，我们发现学过和这个最最有关的知识点应该是 “最大子段和” 。那么对于这道题的最大子矩阵应该怎么办呢？我们可以先参考一下最大子段和的代码。其主要思想就是能选就选，选不了就重开。
那么现在的问题是是否可以把最大子段和的思路借鉴到最大子矩阵中。矩阵本质上是一堆子段叠在一起得出的，且这些子段长度相等，一一对齐，才构造出了矩阵。我们将矩阵从上往下数的第一个子段称为第一行，那么一下所有字段的位置都是确定的了。那么我们就可以更具这个性质压缩一个矩阵。详见下图：
按照这个方法，我们把这个矩阵的第一行确定（假设是 $i$ ）后，假设当前矩阵是 $k$ 行，那么就把给出的矩阵中的第 $i$ 至 $i + k -1 $ 行拿出来压缩。然后对于压缩出来的东西求最大子段和就可以了
我们设 $dp[i]$ 表示宽度（每一行的长度）为 $i$ 的最大子矩阵，答案就从所有里面最大的找。详见代码。
代码12345678910111213141516171819202122232 ...
POJ1742 Coins
题面大秦 为你打开 题目传送门
题目翻译：
有 $n$ 种面值的硬币，面值分别为 $a_1,a_2,…,a_n$ ，数量分别为 $c_1,c_2,c_3,…,c_n$ ，请问在这些硬币的组合下，能够组成多少种不超过 $m$ 的面值。
思路显而易见的，这是一道多重背包模板题。面值是体积，数量就是每一种物品数量，$n$ 是物品个数。
但是这里的题目是 “能够组成多少种不超过 $m$ 的面值 ”，所以设定如下状态：
12dp[i]// 表示是否可以组成面值为 i 的方案
往下就是正常步骤了，详见代码。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<bits/stdc++.h>using namespace std;int n, m;int a[110];int c[110];int top;int v[100010];int dp[100010];void Input() { scanf("%d%d&quo ...
多重背包
前置知识01背包 和 完全背包 喵！
概念：什么是多重背包相较于01背包和完全背包，更实际的，多重背包是每一个物品有个数限制的背包，这相较于前面两个就有一点点难度了
思路：设计多重背包首先，最最最基础的，我们可以像完全背包那样，暴力枚举每一个物品选多少次，代码时间复杂度是三次方的。
1234for(int i = 1; i <= n; i++) // 枚举物品 for(int j = 0; j <= v; j++) // 枚举体积 for(int k = 0; k <= s[i] && k * c[i] <= j; k++) // 枚举决策 dp[i][j] = max(dp[i][j], dp[i - 1][j - k * c[i]] + k * w[i]);
那么，我们考虑更优的方式去选择物品。
当你面对一些奇奇怪怪的优化分组没有思路的时候，你就可以稍微考虑考虑二进制。二进制拆分，因为二进制转变为十进制的唯一性，所以我们对于物品数量二进制拆分可以优化到 $O(n\log n)$ ，代码如下：
1234 ...
