写在前面的话
建议先看概要，然后做题，再看具体的每一道题。
状压DP
概要
基础就不说了（因为我不会FWT，所以把CF622C删了）。
CF453B
由于题目中说$b$两两互质，所以$b$的因数必定不会重合，又因要使$\sum{|a_i-b_i|}$最小，所以$b_i \le a_i \times 2 = 60$，因此$b$的因数$\le 60$，只有$17$个，所以直接状压$dp_{i,s}$表示前$i$个$b$的元素，覆盖了$s$的质数的最小代价。
CF678E
因为初状态不确定，考虑从末状态倒推回初状态，即$dp_{i,s}$表示目前活着的人为$s$，上一场活下来的人是$i$，$1$号最终活下来的概率，转移即为枚举下一场$i$与谁决斗、是否活了下来，再在所有可能中取$\max$。
减少DP状态
概要
有时虽然看上去是暴力的DP，但是也许某一些维可能不会用满，于是便可以优化。
CF505C
乍一看$dp_{i,j}$表示跳到$i$，前一步跳了$j$的答案，但是似乎是$O(N^2)$的，但是注意到即使$d=1$，到最后$d$也是$O(\sqrt{N})$级别的，所以实际上$j$的有效范围只有$[d-400,d+400]$，于是就可以做了，复杂度$O(N \sqrt{N})$。
整体减不合法
概要
其实原文叫做Change the object to dp，但我觉得这其实是一个减少DP状态的特例，又套上了一个整体减不合法的一个经典问题，于是就单独拎出来讲。
不单独讲题了，因为到目前为止似乎只有CF559C和CF722E用到了。
题目概要：一个$H \times W$棋盘上（$H,W$在$10^6$左右），有$N$特殊点（$N \le 2000$），求从左上角走到右下角且恰好经过$m$（$m \le 25$）个特殊点的方案数。
套路：
先将特殊点按$X$为第一关键字、$Y$为第二关键字排序，并把点$(H,W)$加入特殊点中，此时就变成了恰好经过$m+1$个特殊点的方案数了。
首先观察到$dp_{i,j,k}$表示走到$(i,j)$经过$k$个特殊点肯定不行，可以发现上述的dp值会发生实际变化的地方只有每一个特殊点，所以可以只用考虑特殊点之间的转移。
先来看看简化版，$m=0$的情况：
定义$dp_i$表示从$(1,1)$走到第$i$个特殊点且第$i$个特殊点是经过的第一个特殊点的方案数。转移则考虑整体减不合法，即枚举经过的第一个特殊点：
\[dp_i=\dbinom{X_i+Y_i-2}{X_i-1}-\sum_{X_j \le X_i,Y_j \le Y_i}{dp_j \times \dbinom{X_i+Y_i-X_j-Y_j}{X_i-X_j}}\]
于是对于$m \ge 0$，可以定义$dp_{i,j}$表示到特殊点$i$，至少经过了$j$个特殊点的方案数，转移便枚举恰好经过$j$个时的特殊点，答案做一下差即可。
Open and Close Interval Trick
概要
想不到短的中文名，就暂时用原文吧（
问题概述：一个长度为$N$的序列，要求选定一些（可能是固定数量也有可能是任意数量）区间，其中区间两两之间左右端点不重合（设两个区间为$i,j$，则有$l_i \ne l_j $且$r_i \ne r_j$），求方案数（有可能会有其他限制条件，但思想是一样的）。
套路（设选中区间数量任意）：
一起考虑所有区间，同样还是从左到右扫，设构造到了$i$，那么现在所有区间的状态可以被划分为三类：
-
已经结束（$r \le i$），称作
Closed。 -
开始但未结束（$l \le i < r$），称作
Opened。 -
还未开始（$i < l$）。
可以发现$i$关心的只有前两种，于是可以设计DP状态：$dp_{i,j}$表示前$i$个，到第$i$个后还是Opened的区间有$j$个的方案数。
考虑转移，可以发现我们在第$i-1$到$i$的途中只可能会有$5$种操作：
-
什么都不做，使所有
Opened的区间全部延长$1$，$dp_{i,j}+=dp_{i-1,j}$。 -
Open一个
Opened区间，$dp_{i,j}+=dp_{i-1,j-1}$。 -
Close一个
Opened区间，$dp_{i,j}+=dp_{i-1,j+1} \times j$。 -
Open一个
Closed区间，即开了就马上关掉，$dp_{i,j}+=dp_{i-1,j}$ -
Close一个
Opened区间，Open一个Opened区间，$dp_{i,j}+=dp_{i-1,j-1} \times j$。
注意只能Open或Close一个，因为有区间两两之间左右端点不重合的限制。
CF367E
因为两两互不包含，所以当Close一个Opened区间的时候只有一个最先Open的那一个可以，没有系数，并且不可以Open一个Closed区间。$x$的限制就直接转移的时候判一下，强制Open。对于固定的$n$个区间，再在$dp_{i,j}$的基础上增加一个$k$即可。
CF466D
因为每一个数的增量是确定的，设为$d$，所以对于每一个$i$，有意义的状态只有$dp_{i,d}$和$dp_{i,d-1}$，所以是$O(N)$的。
CF626F
首先先将序列排序，那么实际上某个组的代价就是下标最大的减下标最小的，实际上就是两个下标的区间差分和。那么题意就可以转化为概要中的题意，只是要求所有区间的和$\le k$而已。
就可以设计DP状态：$dp_{i,j,k}$表示前$i$个，到$i$后还有$j$个Opened区间，到现在为止和为$k$。由于每一位的差分确定，所以下一个DP的第三维也就是确定的，即是$k + j \times$差分，又因为每个数只能属于一组，所以不能同时Open和Close，所以转移只有四种：
设$l=k+j \times (a_{i+1}-a_i)$，$v=dp_{i,j,k}$，有：
-
选一个
Opened区间加入并保持Opened，$dp_{i+1,j,l}+=v \times j$ -
Open一个区间，$dp_{i+1,j+1,l}+=v$
-
Close一个区间，$dp_{i+1,j-1,l}+=v \times j$
-
Open一个
Closed区间，$dp_{i+1,j,k}+=v$
答案为$\sum_{i=0}^{k}{dp_{n,0,i}}$
连续段DP
概要
问题概述：要求构造一个排列，满足一些性质，或是有一些代价，性质或代价通常与相邻两项大小或差有关，求方案数或最值的一类问题。
套路：
考虑从小到大依次将$i$插入，那么到$i$插入后，这$i$个数一定构成了一些连续段（设有$j$个），但我们不关心每一段具体是什么，也不关心段与段之间的距离。所以说“连续段”，实际上就是强制要求不能再把数插到一个段中间的位置去，并且人为规定两个相邻的段不紧贴。
通常来说，基础的DP定义通常是$dp_{i,j}$，表示前$i$个，分成了$j$个连续段，那转移的时候就会有几种情况：
-
新开一个区间，可以插在空隙之间，$dp_{i-1,j-1} \to dp_{i,j}$
-
在某一个已有区间的两边添加，$dp_{i-1,j} \to dp_{i,j}$
-
将两个相邻区间通过$i$相连，$dp_{i-1,j+1} \to dp_{i,j}$
P5999
因为在最终的排列中，不能出现连续三个的上升或下降子串，所以在DP中我们不能在一个已有区间的两边添加，只能新开或连接。
CF1515E
首先，还是分三种情况讨论，但是情况可能会更多：
-
在某一个已有区间的两边添加时，可能会隔一个开，这样中间的自动就开了。
-
在连接相邻两个时，不能向$i+1$转移（因为要是只隔一个的话早就自动开了），只能向$i+2$或$i+3$转移，注意系数。
CF704B
首先如果我们从小到大插入，那么比到$i$时已经构成段的一定比$i$小，所以实际上$i$对之前的和之后的贡献都可以直接拆分开来：$i$与$i$之前的贡献延到$i$时计算，$i$与$i$之后的贡献提前到$i$计算。所以实际上每一个数的贡献就相对独立了。
对于起点与终点的限制，实际上是简化题意，到$s$或$e$时特判一下即可，注意$s$和$e$的贡献是没有左或右的。
LOJ2743
与上一道CF704B不同，它没有指定$s$和$e$，所以必须增加两维来表示终点与起点有没有被覆盖过，再加一维表示当前的和，转移与上一道类似。
实现比较繁琐，注意细节。
