\(\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{考慮優化的時候可以嘗試把狀態當做限制（條件）來提前，從而避免原先必要的枚舉}\)