写完了。。还有很多坑没填。。。
DP 选讲
例题
AGC 034 E
我们考虑，如果两个棋子呈祖先关系，显然不会选择它们俩（不优秀）。否则，必然是选择两个点，它们的 dist 分别 - 1。
然后考虑可以把棋子拆成 $dist[u]$ 个棋子然后放在它到根的路上，然后相当于可以选择两个不同子树的点削除。
于是考虑枚举最后的根 $rt$ ，然后考虑它的所有子树，其中有一个最大（棋子最多的）的 $u$ ，我们考虑分类
- 如果当前 $sum - max \geq max$ 那么 $F[u] = \lfloor\frac{sum}{2}\rfloor$ ，因为我们可以选择最大的和次大的来消，剩下的必然还有 $sum-max\geq max$
- 否则，最大的子树需要自己来削，$F[u] = sum-max + \max\{k | 0\leq k\leq F[v],2k\leq 2max - sum\}$ ，其中 $ k $ 代表被自己削的。
CF 908 G
每个数字的贡献可以表示成 $10^i$ 的形式，就是它的位置乘上 $10^i$
所以 $ans = \sum_{dig} dig\times c(dig) = \sum_{dig} \sum_{i\ge dig} c(i)$
最后那一步相当于一个考虑每个 $c(i)$ 的贡献，类似差分一下。
而 $\sum_{i\ge dig}c(i)$ 就取决于不小于 $dig$ 的数位个数
$F[i][n][0/1]$ 表示当前在 $i$ 位，有 $n$ 个数字满足不小于 $dig$ ，$0/1$ 表示大小关系。*
答案也可以直接放到 $F$ 里面
AGC 024 F
我们考虑对于所有串 $S$ 计数它是多少个串的子序列。
我们假设 $(S,T)$ 为当前有一个字符串 $S$ ，我们要往后面加一些字符 $T’$ 并且是 $T$ 的一个子序列，转移类似子序列自动机来走，对于每个 $i$ 处理出 $nxt[i][c]$ 表示 $i$ 后面第一个 $c$ 的位置。
- $T’ = \varnothing$ ，相当于走到了 $(S,\varnothing)$ 就是不再加字符了
- $T’ = 0$ ，找到 $T$ 中第一个 0 ，跳过去，转移到 $(S+0,T+t_0)$
- $T’ = 1$ ，找到第一个 1 ，跳过去，转移到 $(S+1,T+t_1)$
根据前面的分析，显然 $(\varnothing,T)$ 可以走到 $(S,\varnothing)$ 就等价于 $S$ 是 $T$ 的子序列，并且这样的路径是唯一的。
每个状态满足 $|S|+|T| \leq N$ 所以总的状态数量是 $O(n2^n)$ 的。
然后就是对于一个 $(S,\varnothing)$ 算出有多少个起点可以到达它，可以直接设 $F(sta)$ 表示有多少条路径，并且由于路径唯一，路径的个数本质上就等价于有多少个起点可以到达它。
某位歌姬的故事
区间最大值为 $h$ ，相当于区间内都小于等于 $h$ 并且必须存在 $=h$ 的。
然后我们可以求出每个点的上界 $up_i$ 就是每个限制的区间不超过 $h$
然后现在我们需要让每个区间都有一个数字等于 $h$ 。显然这个位置必须有 $up_i=h$ 。
然后我们对于每个 $h$ 的限制以及上限为 $h$ 的点拿出来 dp，我们现在要干的事就是在很多个区间里面选择至少有一个点 $=h$ 。
我们设 $F[i][j]$ 表示当前考虑到 第 $i$ 个点，上一个等于 $h$ 的在 $j$ 这个位置。
复杂度 $O(m^3)$
笛卡尔树 dp
笛卡尔树是一个 Treap，满足左边小于右边（编号），并且根是优先级（元素）最小的。
1 | void build_tree( int l , int r ) { |
性质
- 每个排列的笛卡尔树唯一。
- 大小为 $n$ 的二叉树，我们可以还原出这个排列。所以笛卡尔树和排列是一一对应的。
- $u$ 的子树显然是一个区间，并且是一个满足以 $u$ 为最小值的极长区间。
- 对于一个节点 $[l,r]$ 它的父亲要么是 $l-1$ 要么是 $r+1$
然后一些 dp 会以笛卡尔树为背景。比如我们要求某种排列的个数，可以考虑求笛卡尔树的个数。或者给你一个排列或者序列，可以考虑建立出笛卡尔树做树形 dp 之类的东西。
例题
BZOJ 4380 Myjnie
我们尝试把洗车价格的笛卡尔树建出来，一个人来洗车：
- 直接覆盖了当前这个根代表的区间，那么就是看看根是否大于 $c_i$
- 如果没有包含，它处于这个根的左子树，所以它会进入左子树洗车
- 在右子树，去右边洗车。
$F[i][j][k]$ 考虑区间 $[i,j]$ 的最小值为 $k$ 的最大收益，我们只考虑洗车区间在 $[i,j]$ 里面的情况。
转移就是枚举最小值的位置在哪里，就可以用 $F[i][x-1][p\ge k] + F[x+1][j][q\le k] + cost(i,j,x,k)$ 来更新它。其中 $cost(i,j,x,k)$ 就是包含了的贡献。
BZOJ 2616 PERIODNI
我们还是先类似建立笛卡尔树，先找到最小的那个，然后把下方那个矩形拖出来，重复这样的过程。
然后对于每个最小的点，其实代表了一个底层的完整的矩形，我们考虑当前这根为 $u$ ，先吧它的子树里面所代表的矩形，放一下，然后再考虑当前这个矩形，比如在子树放了 $k$ 个，那么一共有 $k$ 个列已经被占了，当前的这个矩形的列就有 $k$ 个不可用，但是当前这个矩形的行都是可用的。
设 $f[u][k]$ 表示 $u$ 的子树里面放了 $k$ 个车的方案数那么当前这个矩形就只能在 $siz[u] - k$ 列上放。放 $x$ 个车方案数量大概就是 ${siz[u] - k \choose x} \times {h[u] - h[fa] \choose x}$ 。
AGC 026 D Histogram Coloring
$F[u][0/1]$ 表示 $u$ 的子树是否是黑白相间的。
考虑，第一行是黑白相间的，那么后面都必须黑白相间，有反色和复读两种情况。而如果第一行不是黑白相间的，那么下一行的构造就只能反色，所以一个第一行不是黑白相间的情况对应唯一一种方案。
然后我们可以直接算出第一行的状态方案数，然后在笛卡尔树上做，它在笛卡尔树上的儿子们都需要 * 2 并且统计进这个东西，因为它的儿子们都可以是反色或者复读。
摩天大楼
我们把元素从大到小放到正确位置时，则插入一个元素其所在连续段就会对应一个笛卡尔树的子树。
在某一个时刻，如果有个位置放了个数，它旁边还没放数，那么它们的差值至少都是 $A_i - A_{i-1}$ ，如果 $A_{i-1}$ 被放进去了，那么这个位置就被钉死了，必然差值是 $A_i-A_{i-1}$ 否则，它的预计的差值会加上 $A_{i-1}-A_{i-2}$ 。
也就是说如果出现了一个位置有数它旁边没有数的情况，并且填了个非这个位置的数字，那么差距就被拉大了一步。
如果当前有 $c$ 个空位，那么差距就被拉大了 $c(A_x-A_{x-1})$ 。现在考虑空位的个数，显然一个快会贡献两个空位，当然除开最左和最右边界是否被顶着。
$F[i][s][x][0/1][0/1]$ 表示第 $i$ 个元素，当前差值为 $s$ 连续段数量为 $x$ ，序列的左右端点是否被顶着。
然后转移就是考虑这个点被插到了哪里。分情况讨论，有可能是插入到一个空的地方，插入到哪个块的左右，或者合并了两个块。
（看起来就好毒瘤啊）
最后复杂度是 $O(n^2L)$
Tree Depth
考虑 长度为 $n$ 的有 $k$ 个逆序对的 dp ，就是你考虑 $1,n-1$ 插入后插入 $n$ ，那么它可以让数量增加 $[0,x-1]$。
或者我们可以决定最后一个值和前面值的相对大小，来决定逆序对数量。这里采用第二种方法。
我们枚举一个 $j$ 是 $i$ 在笛卡尔树的祖先，我们把插入过程分成两个部分：先从 $i$ 开始到 $j$ 决定，那么 $j$ 能够新增的逆序对数量就是 $[0,0]$ 而除开 $j$ 之外都是正常的 $[0,i-p]$。
然后 $i$ 的右边就是 $[0,i] , [0,i+1] ,… , [0,j-1]$ 也是一样的。
如果 $j$ 在 $i$ 的右边，那么新增数量必须是 $[j-i,j-i]$ 。
所以除开必须作为 $i$ 祖先的元素，其他元素的贡献都是和原来一样的。
设生成函数 $p_i(x) = \sum_{j=0}^i x^j$
那么原本答案就是 $[x^k]p_0 \cdot p_1\cdot p_2\cdots p_{n-1}$
如果我们要 $j$ 是 $i$ 祖先，那么就是要除掉 $p_{j-i}(x)$ 乘上 $x^{0}$ 或者 $x^{j-i}$
乘这个的过程其实就是个背包 dp
然后可以先枚举 $j-i$ 然后撤销乘这个值，然后枚举所有这样的 $i,j$ 来乘就好了，复杂度是 $O(nk)$
Hero Meet Devil
又来了
考虑 $f[i][j]$ 表示 $T$ 前 $i$ 位和 $S$ 前 $j$ 位 LCS。
然后我们设 $F[i][S]$ 表示考虑 $T$ 前 $i$ 位，dp 数组是 $S$ 的方案数。
然后考虑到 $f[i][j-1] \leq f[i][j] \leq f[i][j-1] + 1$ 这个很显然。
所以我们只需要 $S$ 记录相邻两项的差值 (0/1)
然后枚举转移。
复杂度 $O(m2^n)$
LOJ 6274
假设我们知道 $x\or y=T$ 设 $x\and y = M$ 那么我们现在判断一下是否可行。
于是我们设 $f[i][0/1][0/1][0/1][0/1]$ 表示 当前在 $i$ 位，当前 $x$ 与 $Lx , Rx$ 大小关系， $y$ 与 $Ly,Ry$ 大小关系。
然后这个也是个 bool 表示是否可行。
于是转移就是我们枚举这一位 $x,y$ 是 $0/1$ 然后判断和 $T,M$ 是否相符。
$F[i][S]$ 表示当前到 $i$ 位，dp 状态为 $S$ 的 $M$ 的数量。刚刚那个 $f$ 的状态也是一个纯 0/1 的数组，所以可以记下来。
插头dp
就是帮zbww打暴力写过的一种维护轮廓的状压dp。
例题
Domino Coloring
统计 $nm$ 的棋盘可以被 黑白相间 的骨牌精确覆盖。
我们假设已经知道了一个轮廓线，那么我们可能放一个竖着的骨牌，一个横着的骨牌。
大概就是记录轮廓线然后讨论一下新增的点。
然后我们还需要用一个 dp 求解原问题，就是把上面的插头 dp 压起来，假设 $F[i][j][c][V]$ 表示用插头 dp 的顺序转移到 $(i,j)$ 轮廓线上颜色是 $c$ ，每个 dp 的结果为 $V$ 的方案数。
打表发现状态数量不到 2000。
实现可以用一个 pair 表示状态本身和方案数量，然后用 vector 来搞。（不太会）
$F[i][j]$ 做一个 vector 来做。
决策单调性
分治：比较好写，有些时候不能分治。
决策队列：存 $[l,r,k]$ 表示 $[l,r]$ 决策点是 $k$ 。
CF 868 F
它又双叒叕来了
Mowing Mischief
考虑按照 $LIS_i$ 分层来 dp ，
然后可以证明满足决策单调性，所以我们知道每个点的决策有一个区间限制，线段树优化，每个点维护一个该区间的决策队列。
杂题
CF 1110 H
掉线了。。。