DP 及其他一些 tips

· · 个人记录

DP 根本不会定义状态怎么办！！！根本想不到。

要看的

PS：感觉最近见到比较多的在序列中的数或平面上的点之间连边建图最后发现是一堆环/链然后跑背包。

PS：基环树上 DP 其实一般就是环上 DP + 树上 DP，环上 DP 的常见套路，一个是考虑删掉一条边破为链然后做环长次 DP，一个是将环复制一份接到后面变成一条链，这个时候转变为序列线性 DP，可能会用到某些决策优化方法。

PS：折磨了我很久的分离子序列问题！

PS：有的时候正着 DP 不太方便或者有对后面的依赖，可以考虑倒着 DP。

PS：如果 DP 过程的状态转移是一堆奇怪的式子，就考虑把这个式子拆开，跟 i 有关的放在一起，跟 j 有关的放在一起，两个分别计算。

PS：如果一维状态存不下或者不好转移，那就再开一维。把转移推出来再考虑优化。

PS：如果背包的时候要求去掉一些物品，直接把那些物品的贡献回退就行了。（但这个也不是通用的，不行的话就直接去掉然后做背包）

PS：如果 DP 数组的某一维开不下，那就考虑是不是这一维能用矩阵优化做！特别是一些很像递推的式子。

PS：有一些状压 DP 的思路就是从 dfs 转化而来的，这种状压通常会显得比较模板，如 P7296，以及 NOIP2021 数列 的 50pts 部分分。

个人觉得常见的一些设计：

$dp_{i,j,0/1}$ 表示前 $i$ 个数里有 $j$ 个满足某性质，其中 $i$ 满足/不满足。（更加套路） $dp_{i,j}$ 表示前 $i$ 个数做完，第 $i$ 个数的限制跟 $j$ 有关。 $dp_{i,j}$ 表示第 $i$ 次操作时第 $j$ 个数的状态。 $dp_{i,j}$ 表示已经进行了 $i$ 次操作，其中有 $j$ 次是特殊的。（跟第一种比较像） $dp_{i,j}$ 表示决策到了第 $i$ 个数，第 $j$ 个位置。（背包） $dp_{a_i}$ 表示值为 $a_i$ 的情况。（只是提醒可能会出现值域上 DP！） $dp_{i,j}$ 表示决策进行到 $a_i$ 和 $b_j$。（这个是 $n^2$，真考到的话比较容易识别）（如果更多个数组就以此类推变成更多维，维数再多的话其实就去考虑状压了） $dp_{i,S}$ 表示决策到第 $i$ 个点（也有决策完前 $i$ 个点的定义），已经选择/已经决策了 $S$ 这个状态里的所有点。 $dp_{u,S}$ 表示在以 $u$ 为根的子树中的决策结果，其中 $u$ 满足 $S$ 所表示的性质。（树形 DP 中很常见，但怎么定义 S 也很难想，一般和穿过 $u$ 的树链，或者 $u$ 本身有没有做操作有关） $dp_{u,i,(0/1)}$ 表示在以 $u$ 为根的子树中选择了 $i$ 个点满足某性质，（其中 $u$ 满足/不满足）。（这种常用于树形背包） $dp_{l,r,(S)}$ 表示决策了 $[l,r]$ 这一段区间，（使这段区间满足 $S$ 所表示的条件，这种定义常见于带限制的括号串题）。（区间 DP 万年套路） 数位 DP 不会，摆了。（其实数位 DP 的重点也并不在 DP 上。） 其实状态想出来的话转移就不怎么难了，除了一些特别丧心病狂的转移时要大分讨的题目。 单调队列优化一般用于转移需要在前面某一段取最大最小。 线段树优化一般用于当前层要取上一层某区间最大最小或者区间和，同时要支持 DP 数组的区间更新。（没怎么见过所以也不太会） 决策单调性优化和斜率优化很多时候是互通的，大概都类似于“如果在转移到 $i$ 的时候决策 $j$ 优于前面的所有决策，那么在 $i+1$ 及以后的状态转移中 $j$ 都优于前面的所有决策”。这种一般要证凸，不过更多时候就是感性理解，或者打表。 四边形不等式优化是什么东西？ --- 分治常见的两种： 一种是 `work(l,r)`，也就是把一个序列断成左边右边分别做，这种也有对序列建笛卡尔树然后跑左右子树分治，不过那样就更像树形 DP 了。 上面那种还有一个扩展形态是 `work(l1,r1,l2,r2)`，常见于两个序列的合并等等操作，比如归并排序，或者 CF1601C。 一种是**根号分治**，反正怎么做怎么不会。比较典的题目是跳，诸如 CF1619H 这种 $i \to p_i$ 的题目。类似于长链剖分的跳链（只是举例，长剖虽然是根号算法但不是分治），LCA 倍增跳父亲（这甚至不是根号算法，但其实根号处理跳的过程本身就很像倍增）。 其实也有一种比较常见的是 $n$ 和值域同级，然后以 $\sqrt{n}$ 为界在两者上分别有优秀的暴力，例如 CF1654E。 还有树上根号分治！通常是按照子树大小或者深度分为小点和大点，小点直接遍历，大点处理次数不超过根号。 根号分治经常跟分块相提并论，其实思想相似但实现是不一样的。分块更类似数据结构，根号分治就纯粹是算法上的东西。注意 $n\sqrt{n}$ 这东西跑 $10^5$ 也是松的。 --- 最近总是能在奇怪的地方见到树状数组和并查集，不得不说这两种东西又好写又难想确实很容易考到啊。 赛时一定要想哈希！最近见到的 Hash 常用于字符串比较，但是像 Sum hashing 和 Xor hashing 这种东西也有些可能用到。