巧妙的dp优化方法

\(\color{green}\textbf{[记录一种巧妙的dp优化方法]}\)

这是一种巧妙的优化状态的方法，通过把状态提前（或者说是把状态转化为限制）的方法来避免记录一些别的信息，这种优化方法相比起数据结构优化更加强大，故作文记之

\(\color{blue}\textbf{[例题]}\)
CF1679E Typical Party in Dorm
P8329 [ZJOI2022] 树

首先是上面那一道 CF 题，先考虑计算每个区间的贡献，先 \(n^2\) 枚举可能形成回文的区间后，考虑有多少情况能够是其产生贡献，目前已知的信息就是在这个枚举的区间中使用了哪些字母来填充问号，接着比较正常的思路就是考虑枚举超集表示在这个串中总共使用了那些字母，然后就是用枚举的超集来计算在这个枚举的回文区间之外的问号有多少种填法，是 \(O(n^3)\) 的，会超时。考虑到我其实关心的并不是超集的元素而是超集的大小，因此我就可以优化。
考虑我直接钦定总共使用了 \(x\) 个元素，然后设置 f[x][S] 表示我钦定使用了 \(x\) 个元素的情况下，目前已经使用了 \(S\) 内的元素，接着高维前缀和，在这么多状态中，只有 f[bitcnt(S)][S] 是合法的。

再看 [ZJOI2022]树 ，正常人都会 \(O(n^5)\) 的 dp ，考虑 f[i][j][k][l] 表示从小往大加点目前已经加到了 i ，在第一棵树种目前能有 \(j\) 个位置给新节点接入，且目前还有 \(k\) 个节点原本钦定了其不是叶子，但是目前还是叶子，在第二棵树中有 \(l\) 个点还没有接上父亲，在转移的时候需要枚举在第二棵子树中会把多少个节点接到当前节点上，然后最后答案的状态就是 f[n][x][0][1] 。
考虑提前第二棵子树的状态，定义 f[i][j][k] ，表示目前从小到大做到 \(i\) ，目前第一棵树还有 j 个口子，而第二棵树钦定还剩下 k 个接口，每次转移点的时候在第二棵树上只需要考虑这个点连到哪个接口以及这个点是不是众多接口中的一个或者只是一个叶子就行了，而到最后只有 f[n][x][0] 是正确的状态，在这里提前了 k 作为限制，从而避免了对于把子树接上来的枚举

\(\color{red}\textbf{考虑优化的时候可以尝试把状态当做限制（条件）来提前，从而避免原先必要的枚举}\)