DP特训总结（技巧篇）
Just_int_mian · · 个人记录
像题解/游记一样的东西挂在这里了。
这里就主要写 DP 技巧了。
1.插入 DP
应该是之前听说过的东西？差不多忘掉了，想了很久才想起来。DP 特训里有两道插入 DP 的题，评讲之前都没做出来，所以专门开了一个技巧来写这个东西。
具体来说，插入 DP 可以用于处理如下问题：
- 要求元素不重复的序列问题。计数偏多，但理论上也可以处理其它的。
因为要求元素不重复，那么直接 DP 就比较困难。所以考虑依次插入每个元素以达到相同效果。更具体地：
- 需要处理块与块之间的问题，可以设
dp_{i,j} 表示前i 个元素有j 块的方案数。每次插入一个数可以进行新开一个块/增加某个块块长/合并两个块等操作。转移都很好推。 - 可以算出合法的插入位置，直接设
dp_i 表示前i 个元素的方案数。转移考虑不插入与插入。
总而言之，有点像区间 DP，是一个很有用的技巧，而且特征比较显著？以后可以看到这种元素不重复就往插入 DP 上想。
2.树形 DP
树形 DP 应当是很熟悉了。但是看 DP 特训的 C 题时发现首先想到的是换根而不是在 LCA 处合并路径，貌似又有点生疏了。
所以这里提到的是一类树形 DP，即处理树上路径信息的树形 DP。对于这种东西，一般有两种做法，换根与 LCA 合并。
如果能在合理复杂度内确定出有根树的 DP 值，并且转移只和父节点和子节点相关（应该是吧？好像暂时没见过其它的。但是理论上和整棵子树相关也是可做的，这里就先只讨论这种情况），那么就可以考虑换根。如果转移是可逆的运算，例如乘法或加法，那么尝试逆掉某棵子树的贡献就行了。但是如果是
LCA 合并就是类似于 DP 求直径之类的东西。这个东西情况不同处理起来也不同，但是呢一般来说都是处理一个向子树内的链的和一个从子树上来的链。还要保证这两个东西不能重合的话，取前缀
树形 DP 的记忆又重拾起来了。特训赛上没做出来 C 的原因是我竟然忘了可以维护次值......好像还是得多练一点才行。
3.容斥
很不要脸地把自己题目的技巧写上去了（什么）。
借用一篇题解里的话就是，用一堆至少容斥出恰好。
当发现一个转移会算重的时候，不要慌张，观察其算重是否有规律，如果发现它被选中的每一个点的每一种组合都会被算重（这里可能有点抽象，意思是假如
然后如果是所有方案数一个
大的技巧已经写的差不多了，当然还有一点小技巧。
- 每次转移方向相反——多重 M 形。
- 不是每个人都有预知未来的能力，类似博弈论的 DP 状态一定要设对。
- 状态能简则简，转移能简则简，对换根这种东西会有很大帮助，无论是思考方面还是实现方面。
- 不仅有二分 + DP
check，还有 DP + 二分找决策点。 - 分清楚需要状压的到底是什么东西，不要看到什么小的数据范围就想状压。
- 状态能简则简。但这里指的是复杂度方面。可能可以把
O(n^2) 的状态去掉冗余状态后变成O(n) 的状态。 - 决策单调性可以尝试画图证明，更加直观。
- 容斥的种类有很多，只会
O(2^n) 的容斥或1,-1,1,-1\dots 的容斥当然是不够的。 - 不要什么都直接想暴力上树啊......可能会浪费很多时间。还有，区间和可以转化为前缀和的差。这个东西听起来可能非常愚蠢但是我写 DP 特训中 I 题时忘了这个然后想实现一个 lazy 单调队列（什么东西）。
- 区间划分？很有可能区间信息和全局信息相同。
- 哇，引射线法。
- 长链剖分？按链长排序说不定会有新奇的发现。
- 当实在想不出来优化的时候，适当暴力上上树还是可以的。
总结的总结
总而言之，这次 DP 特训真的是收获满满。大家选的题都非常优质，我也学到了很多技巧。虽然自己下去还得练，但是应该不会再像以前那么吃力了。那么，希望我的 DP 水平可以提升起来，拥有稳定切紫题的水平！
我们都有光明的未来。