一些DP trick
A
A 题放得好，写一下。
参考 *******。
在一类序列计数/序列极值中，当前元素的代价与两边的元素都有关，并且要求只能是重排，且首尾是容易计算的，我们可以考虑连续段 。
一般的，设 表示前 个元素，现在有 个段，当前代价为 （如果有需要），两边的边界情况为 (可能状压），然后按照某种顺序顺次插入元素，计算代价。
某种顺序 的作用是让计算更为方便 (比如绝对值)。
特征一般为 。
由于非众所周知的原因，某些部分后面来补。
E
E 题可以沿用从小到大插入数值的思想，转换为插入一个数时前面的 个数存在，然后再看它插在哪一个数后面。然后就是加强版的Almost Sorted，套上矩乘。
难点在把值得限制转换为位置得限制。
G
单调性，分段后很显然。
I
转移相关的长度固定，求最值，琪露诺。
B
二分ck的状态很妙，因为一般的树形DP都是对子树内考虑，很有启发性。
和 DMY 的二分+书上背包有同处。
子树内不好求解的，并且认定不能贪心，不能线段树合并，可以想一下这个。
D
trick是用前缀去卡最远的覆盖位置。
与取钱的某个模型的优化方法一样。
以前 myq 找到过一道这样的题，当时对这个技巧惊奇了许久，后面忘了。
H
容斥
正难则反，去求有相同的方案数。
设 表示其中有 个人一样的方案数，转移类似背包。
然后 就是至少 个人一样的方案数。
这玩意是个标准的韦恩图，容斥即可。
C
树上路径一般在 lca 处计算，或者换根。
M
有区修（有可减性），问前缀 min，可以差分。
感觉这题很神秘，有点没透彻，不大顺。
L
贪心可以决定 顺序。
但是如果 顺序不好直接确定，可以往图论上面丢(有最值用dji)。
来自某道 CF 还是 AT。
F
二维的 表示第一行用了前 个，第二行用了前 个是简单地。
考虑优化。
注意到固定 时，当 满足 并且 取最小值时，第二行最多突出一个。这样直接记搜。
感觉这个性质是难观察的。
贪心优化 DP 似乎挺常见，但是难度参差。
最优化的套路见得还是有点少。
容斥仅限于数学部分，还得做点板题。
