動態規劃題目
前置：DP 基礎優化技巧
狀壓 dp 進階
高進制狀壓
一般是地圖類，一次操作影響 \(\ge 3\) 行。一般采用行內 dfs 方式。
也有對于每個點需要有多種狀態的。
P7689 [CEOI2002] Bugs Integrated,Inc.
如果是 \(3 \times 2\)，那么第一行設為 \(2\)，第二行 \(1\)，第三行 \(0\) 就解決了。
如果是 \(2 \times 3\)，第一行 \(1\)，第二行 \(0\)。
于是我們強制欽定 \(2\) 下面填 \(1\)，\(1\) 下面填 \(0\)。
外層枚舉行，以及上一行狀態，然后行內 dfs 轉移即可。
P2704 [NOI2001] 炮兵陣地
放炮的地方設置為 \(2\)，然后依次為 \(1\) \(0\)，只有 \(0\) 旁邊才能放 \(2\)。
P3959 [NOIP2017 提高組] 寶藏
可以很顯然的狀壓，這里需要注意的是必須按層數轉移，可以二進制但需要處理很多函數。
這里采用三進制，\(0\) 表示未擴展，\(1\) 表示之前層的，\(2\) 表示最新層擴展出來的。顯然只有 \(1\) 才能轉移。
這里注意幾個細節，每次擴展為 \(1\) 的最高位即可，如果擴展完，把這一位設置為 \(2\)，雖然不符合定義，但這樣顯然是合法的。如果要進入下一層，把所有 \(2\) 變為 \(1\) 即可。
UVA1412 基金管理 Fund Management
有一種做法就是對于每個狀態設置為 \(9\) 進制數，然后編碼解碼一下。不過太慢了，會超時。
有一個技巧就是對于一些我們發現合法狀態很少的狀壓 dp，可以事先預處理出可能的狀態進行編號以及預處理它們之間的轉移。然后直接按照轉移 DP 就行了。
我的詳細題解在洛谷上，這是我在洛谷的第一篇題解所以寫的很爛。
狀壓雜題
QOJ8005. Crossing the Border
有 \(n\) 個二元組 \((a_i, b_i)\)，將它們分到若干個集合中。劃分方案中的一個集合 \(S\) 需要滿足 \(\sum_{i \in S} a_i \leq m\)，這個集合產生的代價為 \(\max_{i \in S} b_i\)。劃分方案的代價為所有集合的代價之和。求總代價最小值以及對應的方案數，后者對 \(998244353\) 取模。\(n \leq 22\)。
很顯然的暴力，我們將 \(b_i\) 升序排序，然后按照集合右端點從小到大加入保證方案不重，這樣子復雜度是 \(O(3^n)\)。
考慮利用 \(\sum a_i \le m\) 的這個約束，可以想到類似 meet-in-middle 的思想，我們將集合分為兩部分，每部分 \(\frac{n}{2}\) 個二元組，然后進行匹配。
我們可以枚舉一個中間狀態 \(LR\)，表示從左邊選出 \(L\)，從右邊選出 \(R\)，在這個基礎上匹配。我們可以從 \(L\) 的子集內選取集合轉移到 \(R\) 的超集之中。假設 \(L'\subset L\)，\(R \subset R'\)，那么我們需要做的就是 \(L'R \to LR'\)。同樣由于每次我們要加入包含最大右端點的集合，所以 \(L'\) 應該不含 \(\operatorname{maxbit}(L)\)，這樣新加入的部分 \(L-L'\) 滿足最高位最新加入。\(R\) 同理。然后利用 \(\sum a_i \le m\)，我們可以事先對于 \(L'\) 和 \(R'\) 按照 \(\sum a_i\) 排序，然后只需要枚舉 \(L'\)，同時對于 \(R'\) 雙指針即可。
超集和子集需要預處理，并且排序。
這樣子我們相當于枚舉了 \(L\) 及其子集，這是 \(O(3^{\frac{n}{2}})\) 的。同時枚舉了 \(R\)，這是 \(O(2^{\frac{n}{2}})\) 的。所以總的復雜度為 \(O(6^{\frac{n}{2}})\)。
UVA1252 20個問題 Twenty Questions
本質上就是詢問一個最小集合 \(s\) 使得有 \(n-1\) 個物品不包含這個集合。
這題有點難搞的原因是一方面是讓我們最小化，另一方面是讓我們考慮在最劣情況下的答案。是在最壞情況下盡可能小。其實很簡單，只需要在 \(\min\) 里面套一個 \(\max\) 就可以了。設出狀態 \(dp_{s1,s2}\) 表示已經詢問了集合 \(s_1\)，目前確定了物品所具備的特征為 \(s_2\)，還需要至少多少次可以求出答案。
樹形 dp
P10220 [省選聯考 2024] 迷宮守衛
首先注意一個要點，就是滿二叉樹的樹高是 \(\log n\) 級別的，這使得后續復雜度有保障。
最優化排列思路一般是逐位確定，Alice 首先應該最優化第一位，同時最小化代價，可是我們似乎不太方便直接找到最大的滿足條件的第一位。那么不妨二分下 \(x\)，我們需要封堵 \(< x\) 的所有位置，直接 dp 一下最小代價看看是否當前能承受即可。
注意一下，因為我們要求 Alice 要提前設置好所以為了封堵 \(x\) 左右邊都需要設置，所以這里是 \(+\) 而不是 \(\max\)。同時將題目中的提前設置轉化為這里的動態設置也值得思考。
確定了第一位 \(P_1\) 之后，Bob 必然是直接奔向 \(P_1\) 所在葉子節點，然后退出來進行其他訪問。由于是要按照類似 dfs 順序訪問，因此 Bob 活動在訪問完第一個子樹后似乎受到了限制，沒法全局跑來跑去了，但是我們仍然可以對于 Bob 下一次進入的子樹進行二分 \(+\) dp，這樣就完美解決了。
還有幾個細節，算出左右邊的代價之后我們不要著急布置，因為目前的費用肯定是可以支付左右代價的，我們等進入對應位置之后再布置。同時我們發現使用 \(w\) 是有點虧的行為，所以計算的時候雖然是取 \(\min(w_u,f_{rc})\)，但是實際我們發現如果剩余費用可以支付 \(f_{rc}\)，那么就不用 \(w_u\)了，因為 \(f_{rc}\) 這么多費用在進入子樹內是必然要被用掉的。還有一點思考就是提前布置其實違反了子問題一致性結構。
P7091 數上的樹
我們可以生成一個 \(d_i\) 序列表示 \(n\) 的各個約數，其個數其實不超過 \(23327\) 個。對于禁用情況，我們直接不讓其在這個序列中出現就行了。
可以考慮樹形 dp，設 \(f_i\) 表示 \(d_i\) 為根的時候的最小代價。我們發現轉移的時候那個 lca 的貢獻不太好處理。思考一下性質，對于一個數，以它為根的樹的大小是一定的。令 \(g_i\) 為 \(d_i\) 的質因子個數的兩倍減一，\(g_i\) 就是 \(d_i\) 子樹的大小。于是我們 dp 轉移就很好辦了，每次枚舉 \(d_j\times d_k=d_i\) 轉移即可。發現固定了 \(j\)，那么 \(k\) 唯一，如果直接用 map 記錄需要多一個 \(\log\)，可以用雙指針優化。
P4577 [FJOI2018] 領導集團問題
樹上 LIS 模板題。
類比序列 LIS 的 \(O(n\log n)\) 解法，每次在末尾能加入就在末尾加入。不能加入就進行二分然后替換。
使用 std::set 維護這個過程，進行樹上啟發式合并即可。
P4516 [JSOI2018] 潛入行動
樹形上背包 dp
設 \(f_{i,j,0/1,0/1}\) 表示 \(i\) 子樹內放置了 \(j\) 個檢視器，\(i\) 是否放置了監視器，這個點是否被覆蓋了。
暴力合并是 \(O(nk^2)\) 的，其實如果我們把上下界卡死是 \(O(nk)\) 的。
對于兩個大于 \(k\) 的子樹合并是 \(O(k^2)\) 的，但是每個合并完會少一個大小超過 \(k\) 的子樹，所以最多有 \(O(\dfrac{n}{k})\) 次這種合并，復雜度是 \(O(nk)\) 的。
對于兩個子樹合并之后大于 \(k\) 的情況，其實從局部考慮對于每個點只會發生一次這種合并， 所以對于每個點這種合并均攤是 \(O(k)\) 的。
對于合并之后還是小于 \(k\) 的情況，每個點依然是最多匹配 \(k\) 次，所以單點復雜度還是 \(O(k)\) 的。
對于這個十幾種可能的超級合并其實并不需要大分類討論。
設父子分別為 \(u,v\)，現在要 \(f_{v,b,p_2,q_2}\to f_{u,a,p_1,q_1}\)。
在滿足 \(p_1\mid q_2=1\) 的情況下，轉移到 \(f_{u,a+b,p_1,q_1\mid p_2}\) 即可。
QOJ4815. Flower's Land
給定 \(n\) 個點的一棵樹帶權。對于每個點求包含它的大小為 \(k\) 的聯通塊的最大權值。\(n\le 4\times 10^4,k\le 3\times 10^3\)。
先看一個弱化版，求全局最大的聯通塊。
首先是一個技巧 dfs 序背包的 trick，設 \(f_{i,j}\) 表示 dfs 序在 \([i,n]\) 之內的點選 \(j\) 個點構成的背包。由于是要求聯通塊所以要么選兒子要么整個子樹都不選。
于是就有，\(f_{i,j}=\max(f_{i+1,j-1}+a_i,f_{i+sz_i,j})\)。時間復雜度 \(O(nk)\)。
由于是對于每個點都要求，考慮點分治。每次對于分治中心 \(rt\) 旗下所有點 \(u\)，求出同時包含 \(u,rt\) 的聯通塊的最大權值。
分析一下要選哪些點，首先 \(u-rt\) 路徑上的所有點必選（紅筆標出）。
然后將點分成兩類，dfs 序在 \(u\) 前面的（銀+紅），dfs 序在 \(u\) 后面的（橙色，其中三角形代表 \(u\) 的子樹）。
對于第二類點，直接對于 dfs 序 \(> dfn_u\) 的點做一遍背包即可。
對于第一類點其實不好處理，因為其包含了銀色（我們需要加入的貢獻）和紅色（強制要求加入的貢獻），紅色 dfs 序混入了銀色之中很難分離。這里有一個很巧妙的做法，我們將原本遍歷兒子的順序顛倒（代碼實現就是 reverse 一下 std::vector 數組 \(G\) ），這個時候加入 dfs 序 \(\ge dfn_u+sz_u\) 的點的貢獻即可，因為這個時候紅色會和橙色混合在 dfs 序 \(<dfn_u\) 的部分，而灰色正好被分離出來了。
剪枝一下，分治聯通塊大小不足 \(k\) 肯定不優，直接 skip。時間復雜度 \(O(nk\log{\frac{n}{k}})\)。
看了一下官方題解，還有一個更優秀的做法。
設 \(f_{u,i}\) 表示 \(u\) 子樹內選擇 \(i\) 個點可以得到的最大權值。為了求出最后答案，肯定是需要和 \(u\) 之外的一個部分進行合并，所以我們設 \(g_{u,i}\) 表示 \(u\) 上方的一個聯通塊內選 \(i\) 個點可以得到的最大權值。
我們在 \(u\to v\) 的時候求解 \(g_v\)，可以發現其實就相當于在 \(g_u\) 的基礎上加入 \(u\) 點，加入 \(v\) 的兄弟子樹。關于加入兄弟節點，可以對于 \(u\) 的所有兒子進行一個前綴背包和后綴背包，再把 \(pre_{v-1}\) 和 \(suf_{v+1}\) 拼接在一起就可以恰好扣掉 \(v\) 子樹信息。時間復雜度 \(O(nk)\)。
這里要注意一下細節，暴力卷積是 \(O(k^2)\) 的，我們必須把求 \(pre,suf,g\) 的卷積做成類似樹形 dp 的轉移枚舉，才能保證均攤是 \(O(k)\) 單次轉移。
對于 \(pre\) 的求解很簡單就類似于求解 \(f\) 一樣動態更新 \(sz\) 卡住上界。對于 \(pre\times suf\to g\) 的卷積需要注意卷積出來的數組大小必須 \(\ge k-sz_v\) 否則沒意義，這個下界優化也可以將大小枚舉形式規約到樹形 dp 的枚舉形式上。
但是 \(pre\) 的求解就需要小心了，因為我們上述說了還要帶上 \(g_u\)，為了方便直接設 \(pre_0=g_u\)，往后卷，但是如果直接做復雜度還是不對，因為這個形式不符合樹形 dp 一個一個合并子樹了，而是直接就有了一個 \(sz(g_u)\) 的基礎了，一條鏈就可以卡爆。其實 \(pre\) 有用的部分只有 \([k-sz_{suf},k]\) 這么多，因為更小的就湊不出來 \(k\) 了，所以還是可以轉化到樹形 dp 復雜度上。
CF793E Problem of offices
觀察結構，發現一定是形如 a c b d 或者 a d b c 這樣子的結構。
考慮樹形 DP 記錄大小是否可行來湊出題目要求的數據，直接做是 \(O(n^2)\) 的。
使用 std::bitset 優化可行性背包即可做到 \(O(\dfrac{n^2}{w})\)。
閔可夫斯基和 Minkowski
上述是計算幾何版本的 Minkowski，對于離散情況，一般是 \((\max,+)\) 卷積，比如 \(h_{i+j}=\max\limits_{i,j} (f_i+g_j)\) 這種形式。稱 \(f_i,g_i\) 滿足凸性，就是 \(f_i-f_{i-1}\) 和 \(g_{i}-g_{i-1}\) 單調遞減的時候。（當然你改成取 \(\min\)，差分單調遞增也是可以的）。
我們可以用 Minkowski 將原本關于大小平方的卷積優化到關于大小線性。
做法是對于 \(f,g\) 差分之后，取差分前若干大歸并就行了。\(h_0=f_0+g_0\)，然后 \(h_i=h_{i-1}+\Delta _i\)，其中 \(\Delta_i\) 是對于 \(f\) 和 \(g\) 的差分數組進行歸并排序之后的第 \(i\) 大元素。
ZROI2834.念念不忘
有一棵有根樹，其中 \(1\) 號點為根，對于 \(2\) 到 \(n\) 的每個點，\(i\) 的父親為 \(b_i\) \((1 \leq b_i < i)\)。
一開始，每個點上都有一個棋子。每次可以選擇一個棋子，把它往父親方向移動一步。你可以進行上述操作任意多步，但是不能移動 \(1\) 號點的棋子。
每個點有個權值，第 \(i\) 個點的權值為 \(f_i\)。假設最后 \(i\) 點上面有 \(c_i\) 個棋子，問 \(\sum\limits_{i=1}^{n} f_i \times c_i^2\) 的最小值是多少？
\(2 \leq n \leq 5 \times 10^5\), \(1 \leq f_i \leq 10^{12}\), \(1 \leq b_i < i\)。
樹上背包 dp，考慮 \(dp_{i,j}\) 表示 \(i\) 子樹放了 \(j\) 個點，我們發現這是凸的。也就是 \(dp_{i,j}-dp_{i,j-1}\) 遞增。
我們可以用啟發式合并差分數組，取最小前若干的差分即可。
原理是如果差分不遞增的話，我們優先選小的差分會造成某個子節點的第一差分沒選，選了第二差分。這顯然是不行的，因為我們發現如果要選一段差分，必須從頭選，只有最小化且差分遞增的時候才能用。
這本質
CF280D k-Maximum Subsequence Sum
考慮分治解決，可以發現這是一個 \((\max,+)\) 卷積。
由于具有凸性可以考慮 Minkowski 和，同時為了處理多組詢問，放到線段樹上即可。
不過要處理好端點沒取完的情況，我們要記錄端點是否被選擇，如果兩個邊界都被選擇的段接在了一起，就會合并。只需要開兩維 \((0/1,0/1)\) 然后如果合并的時候遇到了兩個 \(1\) 相遇，那么最后的段數也要 \(-1\)。
ZROI2842.六月雪
先做一步最優調整，對于 \(0 1\) 作 \(\pm 1\) 前綴和，發現對于一個和為 \(k\) 的段可以拆成 \(k\) 個權值為 \(1\) 的段是更優的。我們考慮限制一下段的權值之和 \(\le 1\)。
正著做不好做，考慮反過來做，非正的區間我們設其和 \(sum_0\)，那么正的段總和為 \(sum_1=sum-sum_0\)，為了最大化 \(sum_1\)，我們就要最小化 \(sum_0\)，也就是現在要劃分 \(i\) 段非正，使得其總和最小。
假設求出來選 \(i\) 段和最小為 \(f(i)\)，那么答案就是用 \(k\) 中的 \(i\) 來選負段，用 \(k-i\) 個來選擇正段產生貢獻，\(\max\limits_{i=1}^k\{\min(sum-f(i),k-i)\}\)。
現在的問題就變成選 \(k\) 個區間和最小。想一想這種非連續的東西是不太好在 \(O(n\log n)\) 的時間內直接 DP 的，可以用分治。我們設 \(dp_{l,r,cnt,0/1,0/1}\) 表示在區間 \([l,r]\) 中選了 \(cnt\) 個區間權值和最小，0/1 表示左右端點是否閉合。可以發現 DP 是凸的，于是我們直接閔可夫斯基和，也就是對于 \(cnt\) 的 \((\min,+)\) 卷積。這樣子時間復雜度就是 \(O(qn\log n)\) 的。
發現上述分治比較像線段樹結構，于是我們可以使用線段樹維護閔可夫斯基和的過程。
對于一個詢問，外層先 wqs 二分，然后就沒有對于段數的限制了。把詢問區間分成 \(O(\log n)\) 個線段樹區間，對于每個區間的 \(4\) 種 \(\{0/1,0/1\}\) 組合分別找到最優 \(cnt\)，然后合并這 \(O(\log n)\) 個 DP 值即可。
如何對于單個區間找到最優 \(cnt\)？可以發現這是對于凸殼上的一系列點 \((x_i,y_i)\)，找到最優 \(y_i-kx_i\) 的過程。如果直接二分的話會多一個 \(\log\)，但是注意到值域只有 \(O(r-l+1)\)，我們直接開一個桶提前預處理若干最優選擇即可。
雙棧結構優化 DP
通常用于帶刪除的 DP。
小 \(\omega\) 的仙人掌
求最短區間 \([l,r]\) 使得 \((w_i,v_i)~(l\le i \le r)\) 做完背包后權值為 \(w\) 的代價小于 \(v\)。\(n\le 10^4,w_i~w\le 5\times 10^3,v_i\le 2\times 10^5,v\le 10^9\)。
\(\operatorname{Trick}\): 雙棧優化 DP。需要動態加減不可減信息的時候，我們發現線性次數加法是可以接受的，可以考慮這么一個雙棧結構。
比如在本題中，我們發現區間滿足雙指針性質，但是背包不太好減，觀察到值域很小，于是我們可以維護多個背包，然后似乎也有點難辦，因為第 \(i\) 個點的背包是依賴于 \(i-1\) 個點的所以刪掉第 \(i-1\) 個點的背包依然無法消除第 \(i\) 個點背包內 \(i-1\) 的痕跡。
我們不妨維護兩個棧 \(s_1\) 和 \(s_2\)。\(s_1\) 從上到小維護的是 \(r~r-1~r-2\dots p\)，\(s_2\) 維護的是 \(l~l+1\dots p+1\)，其中 \(l\) 和 \(r\) 就雙指針的兩個位置。\(s_1\) 為正著做一遍背包，\(s_2\) 為倒著做一遍背包，這個樣子我們每次移動 \(l\) 指針，只需要彈出 \(s_2\) 棧頂即可，每次移動 \(r\) 是不斷往 \(s_1\) 中加。如果 \(s_2\) 被清空，我們就把 \(s_1\) 中的所有二元組彈出來依次壓入 \(s_2\) 中，這樣子每個二元組入棧兩次，時間復雜度 \(O(nw)\)。
LOJ6515.「雅禮集訓 2018 Day10」貪玩藍月
如果是離線那就線段樹分治。
如果強制在線的話，我們可以類似 deque 的實現，使用兩個對頂棧來維護 DP 的過程。
實現技巧和上一題基本差不多。
字符串相關
ABC240Ex Sequence of Substrings
暴力做法就是把所有子串抽出來進行字典序排序，這個可以在字典樹上完成。
然后每次轉移直接暴力找到位置在它之前的，排名比它小的子串進行轉移，時間復雜度 \(O(n^2\log n)\)。
子串數量已經是 \(O(n^2)\) 了，如果直接對于全體子串為狀態做轉移必然是不可行的。這啟發我們實際有效狀態應該很少，觀察數據范圍大概是要求出現 \(\sqrt n\) 的東西。
之前做字符串題遇到過一個結論就是對于若干個長度和為 \(n\) 的字符串，不同的長度種類的上限是 \(O(\sqrt n)\) 的。本題選取若干個原串不相交的子串也是同理。但是這還是難以完成本題，不過至少提示了我們可以從長度下手。這里要結合字典序的性質下手，如果我們最終選取的子串中相鄰兩個串的長度差 \(\ge 2\)，那么對于長的那個串可以縮短為長度差等于 \(1\)，依然不改變字典序大小關系。
于是我們就可以發現，所選取的子串長度最大也是 \(2\sqrt n\)，我們把所有滿足要求的子串取出來跑最開始說的暴力算法即可。
ACAM 優化狀態轉移
P5319 [BJOI2019] 奧術神杖
乘積式取 ln，轉化為和式的平均數，這可以用 0/1 分數規劃解決。
然后在 AC 自動機上跑 DP 就可以了。設 \(dp_{i,j}\) 表示前 \(i\) 個字符，到了 AC 自動機的節點 \(j\) 所得到的最大權值。遇到關鍵節點就增加權值。
一些常見的模型
區間約束類
通常為給出若干的區間，要求必須滿足區間條件或者完成區間任務可以加分。
一般做法: 以區間邊界為轉移點進行轉移，合并限制發現會有幾個關鍵點，于是 \(pos_i\) 表示上一個關鍵點最晚出現的位置 (\(pos_i < i\))。\(f_{i,j}\) 表示在位置 \(i\) 上一個關鍵點為 \(j\)。注意維度可以壓縮，比如例 1 直接壓掉了第一維。例 3 強制欽定轉移位置壓掉了第二維。
類似的題目有：
下面給出一道例題。
CF1327F AND Segments
1010101010101001 0 01
1100100100101001 0 01 \(\gets\)
1010101010101000 0 00
1001001011011010 1 01 \(\gets\)
1010110101010101 0 11
考慮到二進制的獨立性，所以可以拆位統計。這題拆位又碰上區間，二維限制有點難想。可以畫個圖，那一豎列為拆出來的一位。 兩個箭頭代表區間左右端點，加粗的幾個數字就是一條限制拆位后約束的數字。這樣就一目了然了。
按位與的性質得出，若區間與為1則必須全部為 \(1\)，與為 \(0\) 的話區間至少一個 \(0\)。看起來可以先將 \(1\) 填入，再考慮 \(0\) 的放置，然后計數原理亂搞。但是限制為 \(0\) 的區間有重疊就很惡心。
那就只能 \(dp\) 了。二維 \(dp_{i,j}\) 表示在 \(i\) 位時，上一個 \(0\) 填在第 \(j\) 位的方案數。
- \(j<pos_i\) \(~dp_{i,j}=0\)
- \(pos_i \le j< i\) \(~dp_{i,j}=dp_{i-1,j}\) (上一個 \(1\) 在 \(j\) 處，故 \(i\) 處只能填 \(0\) )
- \(j=i\) \(~dp_{i,j}=\sum\limits_{k=pos_i}^{i-1}dp_{i-1,k}\)
看似復雜度不行，但是列出狀態轉移方程后我們可以驚喜的發現并不需要第一維，直接維護段和即可。這就啟發我們有的時候先大膽列出式子哪怕復雜度爆了，后面再優化。
連續段 DP
P9197 [JOI Open 2016] 摩天大樓
雙倍經驗：P2612 [ZJOI2012] 波浪。
我們將排列放在平面上，可以畫出折線。總和顯然是相鄰縱坐標之差。
考慮對于這個平面進行從上到下的掃描線，在掃描的時候看掃描線與折線交點，然后進行 DP。
維護已經掃描過的點構成的連續段，可以發現連續段內部由于相鄰的已經安排上了所有無貢獻，只有兩個端點朝外有貢獻，這里貢獻提前計算，每次向下移動一格掃描線，就把所有相鄰為選擇的點差值累加 \(1\)。
設 \(dp_{i,j,0/1,0/1}\) 表示目前已經有 \(i\) 個連續段，總和為 \(j\)，第一個數/最后一個數有沒有被加進去的方案數，答案就是 \(\sum dp_{1,\leq L,1,1}\)。
轉移的時候如果掃到了一些位置，有如下轉移：某個位置新開了一個段導致段數 \(+1\)，某個位置合并了兩段導致段數 \(-1\)，某個位置延續了之前的段此時段數不變。
XYD20932.情報傳遞
小 \(K\) 收到了一份情報，他要把這份情報傳給他的所有朋友。他的 \(n\) 個朋友排成一圈，初始所有朋友都不知道這份情報，在每個時刻會發生下面的事：所有知道這份情報的人會將情報傳輸給自己相鄰的兩個人。
然后小 \(K\) 會隨機選擇\(n\)個朋友中的一個將情報傳輸給他（已經收到情報的人還可能再次收到）。小 \(K\) 想問你期望多長時間后他的\(n\)個朋友都能收到這份情報，答案對質數\(998244353\)取模。\(n\le 5000\)。
連續段 dp 好題。
我們設 \(f_{i,j}\) 表示這些線段在環上一共覆蓋了 \(i\) 個點，形成了 \(j\) 個段的概率，\(g_{i,j}\) 表示期望。這些段我們在開始的時候不設置其相對位置關系，只是要求他們不相鄰，否則可以合并成一個段。
每輪，每個段會向左右各擴展一個格子，同時會有一個點被選擇。考慮先一個一個來做，先做擴展。
如果你直接向兩側擴展的話，難以確定當前覆蓋了幾個點，因為可能一個向左，一個向右，二者就重合了。但是如果我們先讓所有的段向左擴展一個，轉移到新數組 \(f,g\to c,d\)，這樣子就可以確定覆蓋點的個數是增加 \(j\) 的。于是有 \(f_{i,j}\times S_{j,k}\to c_{i+j,k}\)，其中 \(S_{j,k}\) 表示把 \(j\) 個無序連續段合并成 \(k\) 個的方案數。由于你之前是無序的，所以新加入之后是要計算一個順序的，比如一個由 \(m\) 個小段合并成的大段的貢獻就是 \(m!\)。
考慮遞推 \(S_{i,j}\)，這個推導類似于斯特林數的遞推。每次新加入一個元素，其可以自己新開一個段，也就是由 \(S_{i-1,j-1}\) 轉移而來。也可以選擇插入原先的段中，一個長度為 \(k\) 的段能插入的位置個數是 \(k+1\)，\(\sum\limits_{1\le z\le j} k_z+1=i-1+j\)，所以也可以由 \(S_{i-1,j}\times (i+j-1)\) 轉移而來。
這樣子就完成了向左擴展，向右擴展也是同理 \(c,d\to x,y\)。
于是 \(x,y\) 就代表擴展了，但是未選擇點的 dp 數組。現在時間流動了 "1"，所以時間的期望要累加對應的概率，\(y_{i,j}\gets x_{i,j}\)。現在要 \(x,y\to f,g\)。下面 \(f,g\) 的轉移相同，只列舉其中一個。
當前選擇的點可以是之前已經選擇過的點，那么不會產生任何新的覆蓋。有 \(f_{i,j}\gets x_{i,j}\times \dfrac{i}{n}\)。當前選擇的點可能是原先連續段旁邊的一個點，這樣子那個段的長度就增加 \(1\) 了。我們可以選擇放在某個連續段的左邊或者右邊，于是有 \(2j\) 個選擇，那么 \(f_{i,j}\gets x_{i-1,j}\times 2j\)。可以新開一個段，由于這里是不帶相對順序的 \(\dfrac{1}{n}\) ，后面合并段的時候會確定這個貢獻。\(f_{i,j}\gets \dfrac{1}{n}\times x_{i-1,j-1}\)。還可以合并兩個段 \(f_{i,j}\gets \dfrac{1}{n} x_{i-1,j+1}\times A_{j+1}^2\)。當 \(j=0\) 的時候代表之前只剩一個段了，我們把它左右端點相接，自己合并自己。注意 \(j=0\) 的狀態代表已經結束不可再別的狀態轉移。
初始狀態是 \(f_{1,1}=g_{1,1}=1,x_{1,1}=y_{1,1}=0\)。因為你第一輪相當于沒有左右擴展的過程，只有選點的過程，所以 \(x,y\) 是 \(0\)。
可以發現第二維的大小為 \(O(\sqrt n)\) 的，于是時間復雜度 \(O(n^2)\)。
網格圖行走凸函數 DP
通常用于在一個二維網格圖上的行走，給出 \(q\) 個點，求到達它們的最小代價。
直接暴力平方 dp 會超時，這個時候考慮維護整體 dp，通常由于貢獻函數為凸函數或者一些取 \(\min\) 操作，會讓 \(f_i(x)\) 是一個凸函數，每次會根據更優的斜率選擇，更新一段前綴或者后綴。
然后這個函數的維護，就是用一個棧來維護，因為你更新的只有一段前綴或者后綴，符合棧的性質。棧內部需要保存這個凸殼的直線信息。保存這個點的橫坐標以及斜率即可，還有一些對全局移動坐標的 tag。然后更新和二分棧維護四邊形不等式是一樣的，直接考慮如果當前棧頂直線整段都不如新加入的直線就把當前直線刪除，如果新加入直線在剛開始就不如棧頂直線，那么直接退出更新，否則在中間二分找到一個交點，滿足交點之前新加入直線更優，交點之后棧頂直線更優，更新信息之后退出。
代碼很有細節這里放一下兩道例題的 Code。
P7294 [USACO21JAN] Minimum Cost Paths P
很顯然的整體 dp 的形式。
我們設 \(dp_{i,j}\) 表示考慮了前 \(i\) 列，走到第 \(j\) 行的代價。
因為貢獻函數 \(j^2\) 是下凸函數，可以猜測，固定 \(i\)，\(dp_{i,j}\) 是一個下凸函數。也就是 \(dp_{i,j}\) 的差分數組單調不減。
每次從 \(i-1\to i\)，對于 \(dp_{i}\) 先是直接繼承 \(dp_{i-1}\)，然后對于每個位置打上一個 \(j^2\) 的標記。
現在考慮列內的轉移。上面說了 \(dp_{i,j}\) 的差分數組單調遞增，而行內觀察形式其實就是差分數組對于 \(c_i\) 進行一個 chkmin。由于差分數組單調，于是我們直接二分找到變化點進行修改即可。
由于第二維是 \(O(n)\) 的，我們不能直接維護。考慮使用單調棧維護轉折點。轉折點之間都是一條一次函數。
直接的思路是維護一個差分數組，這樣子非常方便更新。但是由于不是問 \((1,1)\to (n,m)\) 的代價，而是中間有 \(q\) 個詢問，我們不可能每次詢問都累加一次差分數組吧。
于是考慮維護 \(f_i(x)=(i-j)\times x^2+c_j\times x-b\) 的形式。這個 \((i-j)\times x^2\) 就是上面說的一個 \(+x^2\) 的 tag，其中 \(j\) 表示上次該點被 chkmin \(c_j\) 更新的時間點 \(j\)。由于上次是被 \(c_j\) 更新，所以就是形式就是 \(val_p+c_j\times (x-p)\)，其中 \(p\) 表示前面一個斷點，拆開就是 \(c_j\times x+b\)。綜上所述，我們只需要在單調棧中對于每個斷點維護一個三元組 \((x,j,b)\) 即可。
每次修改由于我們不是直接維護的差分數組，所以可以直接用 \(f_i(x)-f_i(x-1)\) 得到差分值。對于后綴推平，我們可以直接從后綴開始不斷 check 并且 pop，由于每列只會進隊列 \(O(1)\) 個的點，所有點也只會被刪一次，所以復雜度均攤是正確的。pop 到滿足題意之后要二分尋找一下，然后插入新的端點。
每次詢問就是離線處理，二分找到詢問點在棧中哪兩個端點之中，然后求值。
時間復雜度 \(O((m+q)\log n)\)。
云斗NOI R7T1 Function
還是維護整體 dp。可以發現每次加入一條斜率為 \(a_i\) 的直線去更新一段前綴，其中強制要求更新第一個位置，可以發現斜率小的直線代表代價低會逐步取代斜率大的直線，所以最后出來的應該是一個上凸函數。按照上述方法維護這個凸函數即可，具體可以參照上面的代碼。
其實這個凸函數等價于這個貪心：我們的行動一定是先往左上角行動若干步，然后遇到一個最小的列之后直接在這列往上走到底。
ZROI2885. 激光陣
暴力方程 \(dp_{i,j}=\min(dp_{i-1,j}+w_{up},dp_{i,j-1}+w_{right})\)。
線段樹優化 dp
對于這種整個整個往上轉移的，而有明顯的分段特征的，這里的段就是激光的起點在每一行的作為分界點，分界點之間的 \(w\) 不變。可以考慮線段樹維護整體 DP。
發現行內轉移不太好處理，我們要利用同一段中 \(w\) 相同，可以維護 \(dp_{i,j}+w_r(j,n)\)，這樣子行內影響就消除了，每一個位置的值就等價于前綴最小值。
我們只需要處理行間轉移以及 \(w_{up}\) 即可，發現 \(w_{up}\) 的值僅在水平激光端點處變化，我們找到端點后所有端點后的值如果是從上一行轉移的應該整體 \(+1\)。怎么找到從上一行轉移的位置呢，根據前面前綴最小值的性質，我們發現從一個出發應該是一段 \(x,x,x....x,<x,<x\)，這個樣子 \(<x\) 的位置必然不是通過前綴最小值得到的，于是我們只需要找到第一個小于 \(x\) 的位置，然后給那段后綴整體 \(+1\)。
維護差分法
發現這個 DP 轉移式子很有差分的感覺，而且行內具有單調性，于是考慮維護差分。
首先行內轉移的式子規定了差分的上界是 \(w_{right}\)。然后可以通過行間轉移來使得差分更小，大概就是從小到上會有一個 \(w_{up}\)，然后可以用他加上上一行的 \(\delta'\) 來更新這一行 \(\delta\) （初始值是上界 \(w_{right}\)）。模擬從下往上合并的過程，其實如果我們是從小往上合并的話，那么初始值應該是上一行的 \(\delta'\)，然后和 \(w_{right}\) 也就是上界取 \(\min\)，如果是前者小，那么不會發生變化，如果是后者小那就更新 \(\delta\)，同時由于這個地方的值變了，那么會影響下一個 \(\delta_{next}\)，具體來說下一個值應該會變大。模型化，就是那個點有一個容量上界，我們可以往點里面加球，如果球多于上界，就會一直往右傳遞，一直轉移到最后一行每個位置里的球數就是最后的差分數組。每個位置的容量就等于上一行該位置的容量加上新增的向上的激光。
使用 std::set 維護這個過程就行了。
雜題
Public judge NOIP Round #6 抉擇
感覺這種優化到盡頭還無法解決的 \(dp\) 就是要挖掘一下性質。
部分分挺簡單的，但是正解思路其實和特殊性質最后一檔很想，二者的思想都其實是選更多的大概率會更優一點。我們來分析一下為什么不多選，比如選了 \(a_j\) 和 \(a_i\)，我們非要在其中插入的一個 \(a_k\)，那么可能 \(a_k\) 的很多位都為 \(0\)，導致我們損失了一些高位。這里給出一個結論也就是只要 \(a_i~and~a_j\) 與 \(a_i~and~a_k\) 的最高位相同即可，很明顯最高位大于其他位之和。所以我們只需要對于每一位保存最近的即可。注意別忘記考慮按位與為 \(0\) 的情況。
P9870 [NOIP2023] 雙序列拓展
一道優化 dp 的好題目。
下面只討論 \(f_i>g_i\)，方程是顯然的
時間復雜度 \(O(qnm)\)。這顯然不太好壓縮維度或者用數據結構來優化了。
那就需要尋找 dp 性質了。
方法一：將 dp 方程轉為有組合/幾何意義的東西
這里可以變成走方格，從 \((1,1)\) 到 \((n,m)\)。我們發現走不到終點的充要條件是有一個圍了一圈的封堵。這個直接可以雙指針來優化。
方法二：bool 型 dp 提取狀態到 dp 值中。
可是很多類似的題目我們都可以發現對于 \(dp_i\) 并不是需要越大越好，所以不能只記錄一個最大的 dp 值。每題的解決方法都不同，有的題目是觀察出一維度固定另一維度合法的是一個區間，本題是用到了可回退的思想。
我們先最大化 \(dp_i\)。
如果 \(a_i \le a_{i+1}\)，那么顯然是可以的 \(dp_{i+1}\) 在 \(dp_i\) 的基礎上繼續擴展，即找到一個 \(b_j \ge a_{i+1}\)。
如果 \(a_i > a_{i+1}\)，那么不能繼續擴展，我們可以貪心地進行回退，退到第一個 \(b_j<a_{i+1}\)，此時對于 \(a_{i+1}\) 是滿足條件的，可以證明對于 \(\le i\) 的位置也是滿足條件的，因為 \(a_i > a_{i+1}\)，所以 \(a_i\) 對位 \(b_j\) 就可以了。時間復雜度 \(O(qn\log m)\)。
考慮去掉 \(\log\)，我們發現每次回退又向前很重復。這里有一個觀察，如果在位置 \(i \to i+1\) 的時候發生了回退了，如果 \(a_j>a_i\) 那么本次回退是無效的，因為 \(a_j\) 會比 \(a_i\) 走得更遠。于是我們發現只有前綴 \(\max\) 才會對答案產生向前的貢獻且可以抵消之前的回退。回退的時候只需要檢查 \(a_i\) 是否大于 \(b\) 序列的前綴 \(\min\) 即可。需要注意的一點是我們雖然是免去了回退但是后面必須有點可以恢復過來。這就是要求序列的末尾必須是前綴 \(\max\) 特殊性質可以滿足這點。如果不是呢，將序列從 \(\max\) 處分成兩半，前一半順著掃，后一半倒著掃，這樣可以滿足了。
P6847 [CEOI2019] Magic Tree
可以發現約束條件就是子節點被切斷的時間要在祖先節點之前，否則就沒機會切斷了。
于是設出 dp，用 \(f_{u,i}\) 表示在 \(u\) 節點，它和其父親的邊在 \(\le i\) 時刻被切斷所得到的最大價值。
注意這里的 \(f\) 其實是前綴最大值因為定義是 $ \le i$。暴力做的話時間復雜度 \(O(nk)\)。
但是這里是二維的，復雜度顯然不行，一般這種二維 dp 想要優化的話，一般就是第二維通過轉化為圖像或者線段樹合并啥的或者更難點就是找性質。本題第二維顯然是整體 dp 的形式，我們只需要用 STL 或者數據結構維護第二維，每次直接繼承兒子的第二維并且進行 \(O(1)\) 個修改。
本題采用 std::map 來維護。
可以發現有用的點并不多，因此 map 中的第二維信息只有子樹內出現的 \(d_v\)（相鄰 \(d_v\) 之間的 \(f\) 是相同的）。這就會出現一個問題，在合并兩個 map 的時候，假設是 \(rt_u\gets rt_v\)，如果 \(rt_v\) 中出現過的一個值在 \(rt_u\) 中沒出現過，那么對應點累加的時候該點對應的值在 \(rt_u\) 中將會是 \(0\)，這不符合前綴 \(\max\) 的要求啊。于是我們考慮維護差分 \(g_{u,i}\)，可以注意到差分也是可以對應位置相加的且可以自動完成對于空白位置的前綴 \(\max\) 要求。
這樣子我們就完成了 \(\sum f_{v,i}\) 的轉移處理，直接啟發式合并 map，然后對應位置相加即可。
現在要處理的就是單點（\(d_u\) 位置） \(+val_u\)，并且作為前綴值往后更新前綴 \(\max\)。
\(d_u\) 位置 \(+val_u\)，是很好做的，我們直接對于差分數組 \(g_{u,d_u}\gets val_u\)，然后不可在后面直接 \(-val_u\)，因為前綴 \(\max\) 的要求需要保證差分數組恒正。于是我們就直接把中間的一段 \(\sum g_{v,i}\le val_u\) 的差分值直接舍去即可，這一段是暴力往后更新，因為我們可以發現每個點只會進入 map 一次，然后最多被舍去一次，所以時間復雜度均攤是正確的。
還有一種線段樹合并的做法，可以去題解區學習。
CF1476F Lanterns
由于目標是全局覆蓋，所以我們斷斷續續地覆蓋最后再用后面來覆蓋前面空缺的是很難用狀態表示的。
于是考慮記錄一個連續段 \(dp_i\) 表示到第 \(i\) 個燈籠能覆蓋地最長前綴有多長。可是我們如果在中間一段出現一個位置的最優選擇是向后，但是他前面沒有補齊怎么辦呢？
等后面補齊的時候這個位置再往前延展。也就說對于當前的 \(i\) 可以找到一個最靠前的位置 \(j\) 使得 \(i\) 可以覆蓋到 \(f_j+1\)，于是我們便可以在 \((j,i)\) 之內的位置向前延展了。
P3643 [APIO2016] 劃艇
值域過大考慮離散化，然后按照原有端點，分成很多小端。設 \(f_{i,j}\) 表示第 \(i\) 個數的值域在 \([l_j,r_j]\) 之間。考慮轉移的時候，\(k \to i\) 如果值域區間不同還可以轉移，但是如果他們在同一個值域區間內就不好辦了。
那就只能使用大招，強行欽定 \(k \to i\) 的轉移是不同區間的，同時 \(k+1,k+2...i\) 都落在 \([l_j,r_j]\) 之間或者取值為 \(-1\)。小細節：由于狀態設計要求這里的 \(c_i\) 不能取 \(-1\)。設一個有 \(m\) 個數待選擇，那么方案數是 \(\begin{pmatrix} m+Len_j-1\\ m \end{pmatrix}\)。
組合數可以線性遞推。
我們仔細觀察一下求和式子，似乎可以前綴和優化。但是一定要小心，那個 \(m\) 其實是和 \(k\) 有關的，所以我們只能對于第二維進行前綴和優化。
同時可以用前綴和優化，發現第二維求和與 \(i\) 無關，于是我們可以設 \(s_{i,j}=\sum\limits_{z=0}^{j-1} f_{k,z}\)。那么 \(f_{i,j}=\sum\limits_{k=0}^{i-1}s_{i,j}\times \begin{pmatrix} m+Len_j-1 \\ m\end{pmatrix}\)。
注意細節，為了前綴和方便，我們將 \(j\) 提取到第一維進行枚舉。同時，第二維枚舉 \(i\) （倒序）也有利于使得 \(m\) 每次只增加 \(1\)，便于線性遞推組合數。
時間復雜度 \(O(n^3)\)。
P7606 [THUPC2021] 混亂邪惡
綜合了各種技巧的背包題。
設計狀態 \(f_{0/1,l,g,x,y}\)，第一維滾動數組，后面分別表示 \(L,G\) 目前積累的值，然后就是坐標。可以發現每次移動的 \(\pm 1\)，可以用 bitset 優化。然后還有一個經典結論就是隨機游走的期望最大移動距離是 \(\sqrt V\) 級別的，這樣子坐標維度直接開 \(2\sqrt n\) 級別就行了。
CF809D Hitchhiking in the Baltic States
樸素的狀態以及轉移顯然不行，我們可以聯想到 LIS 的更優做法，那就是動態維護長度為 \(i\) 的 LIS 結尾數字最小。
本題也可以沿用該思路，設出 \(f_i\)。那么考慮加入一個數 \(\in [l_i,r_i]\)，這個時候就需要找到所有的 \(f_i<r\)，對應的 \(f_{i+1}= \max(f_i+1,l_i)\)。化簡一下，也就是找到最大的 \(j\) 使得 \(f_j<l\)，此時 \(f_{j+1}\) 必然大于等于 \(l\)，故\(f_{j+1}=l\)，其余的 \(l \le f_i<r\)， \(f_{i+1} \gets f_i+1\)。
必然是數據結構維護，但是第一感得到的線段樹好像并不能有效完成第二個操作。我們發現第二個操作中的 \(f_{i+1}\) 都是強相關于 \(f_i\)，于是可以把 \(f_i\) 右移然后區間 \(+1\)，那么空出來的那個位置怎么辦，其實正好用 \(f_{j+1}\) 來填補。然后末尾多出來一位怎么辦，如果本來就可以讓答案序列增長一位那么就不用管，否則在后面再刪掉一個節點就行了。
UVA10934 裝滿水的氣球
首先確定策略，如果只有一個球那么我們顯然只能從下往上一層一層摔直到確認到位置。如果多一個球，那么實驗次數就減小了。因為我們可以在某次直接到更高層，然后試錯。考慮 dp，由于我們不知道答案樓層是什么，所以樓層不應該放在狀態里面。
設 \(dp(i,j)\) 表示用 \(i\) 個球，實驗 \(j\) 次可以確定最大高度。
本次測試的樓層應該是 \(dp(i-1,j-1)+1\)，因為如果本次氣球破了，保證可以用剩下的操作次數和氣球完成實驗。我們要求的是最高樓層所以應該是要加上最好的情況，也就是氣球沒破，那就還能往上擴展 \(dp(i,j-1)\) 層。于是 $$dp(i,j)=dp(i-1,j-1)+dp(i,j-1)+1$$
- 雖然是加起來，但是意思不是都要進行一次，其實是根據氣球有沒有破碎選擇其中一種方式來繼續詢問。
每次詢問就是找到一個最小的 \(i\)，滿足 \(f_{i,k}\ge n\)，二分即可。時間復雜度 \(O(T\log K)\)。
ABC221G Jumping sequence
發現每一步都選擇一個方向都太難搞了，考慮 \((x,y) \to (x+y,x-y)\) 旋轉一下坐標系，那么每一個方向就是獨立了的，我們每次可以在每個方向上選擇前進還是后退。于是對于每個維度都有
選擇 \(p_i \in \{-1,1\}\)，使得 \(\sum p_i\times d_i=T\)，其中 \(T=A+B，A-B\)。
這很像背包的形式，兩邊同時加上 \(\sum d_i\)，再除以 \(2\)，得
選擇 \(p_i \in \{0，1\}\)，使得 \(\sum p_i \times d_i=\frac{T+\sum d_i}{2}\)。
這是一個 0/1 背包的形式，可以用 bitset 輔助完成。
P10973 Coins
多重背包最大價值可以用單調隊列優化，在 \(O(nW)\) 的時間內求解。
對于求哪些價值可以被構造出來，也同樣是 \(O(nW)\) 的。除了 \(f_j\) 表示價值 \(i\) 能否被湊出來，我們還需要一個輔助數組 \(g_j\) 表示外層枚舉物品 \(i\) 的時候，湊出價值 \(j\) 需要的最少 \(i\) 個數，每次如果個數 \(<c_i\) 就可以轉移。
CF1667D Edge Elimination
構造題目依然可以考慮 \(dp\)。當信息只與子樹有關所以可以樹形 \(dp\)，所以本題可以記錄與父親有關狀態，使得子樹獨立。設 \(f_{u,0/1}\) 表達 \(u\) 與 \(fa\) 刪邊的時候，有偶/奇數條子邊。根據子節點的 \(f_{v,0/1}\) 值種類分為 \(4\) 種。如果全為 \(0\)，那就無解。對于一個 \(1\) 的情況，顯然是在 \(u\) 剩奇/偶數的時候交替刪。如果有兩個 \(1\)，這些東西可以用來平衡。
AGC032D Rotation Sort
本題如果直接去思考變動序列的變化情況，其實是比較難做的。我們并不知道該把目前的數移到哪個位置，因為后面的其他數字變動會影響當前的數字移動的位置。
所以轉化思路，我們考慮哪些是不動了。確定不動的序列（這是一個單調遞增的數列）的之后，其他數字根據相對大小關系就可以確定往前放還是往后放，付出 \(A\) 或 \(B\) 的代價。
設 \(f_{i,j}\) 表示處理了前面 \(i\) 個數，當前不動序列的最后一個數字為 \(j\)。根據 \(a_i\) 和 \(j\) 大小關系，還有是否選擇 \(a_i\) 作為不動序列來轉移。
可能咋一看第一個轉移有點小問題，就是 \(a_i>j\) 不一定是要往后放啊，可能后面的移動到前面這個的位置就正確了。但其實這個決策是被包含在了第三個方程里面所以這個轉移沒有問題。
本題數據小，直接暴力轉移 \(O(n^2)\) 即可。
ARC125F Tree Degree Subset Sum
結論是對于重量為非負數且 \(\le n+1\) 的背包，如果構成某重量，最少用 \(l\) 個，最多用 \(r\) 個。那么 \([l,r]\) 內的任意個數個都可以湊成該重量。
對于一棵樹有 \(\sum d_i=2n-2\)，令 \(d_i\gets d_i-1\)，有 \(\sum d_i=n-2\)，可以套用上述結論。
同時和為定值的數一共有根號種，直接二進制拆分多重背包即可。
P9084 [PA 2018] Skwarki
看到序列最值，考慮對于笛卡爾樹進行計數。
首先有一個觀察就是只會刪除 \(\log n\) 輪。
可以發現每次都會刪除 \(<2\) 個子樹的點，當然最左邊的點和最右邊的點需要特殊討論。
同時由于全局最大值的存在，除了 \([1,n]\) 特殊考慮之外其余每段區間最多有一個邊界。
因此設 \(f_{i,j,0/1}\) 表示將一顆大小為 \(i\) 的笛卡爾樹在經過 \(j\) 次操作后刪光的方案數。其中這顆笛卡爾樹有無邊界點。
先討論無邊界點的情況，這個時候還需要分類討論，一個就是根最后被刪除，一個是兒子最后被刪除。
對于前者需要兩個兒子刪除輪數都是 \(j-1\)，枚舉左子樹大小，用組合數分配一下權值即可。
對于后者，要求一個兒子輪數為 \(j\)，另一個為 \([0,j-1]\)，注意系數還有一個 \(2\) 代表左還有右最后刪除。
有邊界的情況，要么是有邊界的那一側最后被刪光，要么是那一側被刪光之后根擁有了邊界，然后根最后被刪，也是類似轉移。注意這里的第二個轉移沒有系數 \(2\)，因為有一個第三維是 \(1\)，另外一個是 \(1\)，兩個 \(f\) 數組可區分。
上一個前綴和優化，最后在根處特殊處理一下轉移。
對于初始有 \(f_{0,0,0}=f_{0,0,1}=1\)，按照區間大小從小到大轉移即可。時間復雜度 \(O(n\log n)\)。
QOJ7199.Bomb
我們需要連出雙向可達性，也就是所有點在同一個 SCC 內部。
考慮對于一個前綴進行 DP，假設目前已經對于前 \(i\) 個點完成了他們的半徑選擇。那么圖的形態一定是若干段區間在同一個 SCC 內部，且 SCC 是一條鏈，前面的連向后面的，因為我們可以通過后續設計半徑來使得后面某個覆蓋到最前面來合并前面的一系列 SCC。而且我們只關心第一個 SCC 的形態，因為能覆蓋到第一個 SCC，且第一個 SCC 會往后連，那么所有點都可以雙向可達了。
考慮何時第一個 SCC 能發生擴展，假設是從黑色擴展到橙色，需要滿足以下條件
-
有綠色的返回邊
-
兩段之間有一個藍色連邊
-
橙色段內是要從頭到尾串起來（最優形態一定是每一個連向下一個）。
橙色的可以直接前綴計算，綠色也很好寫，但是這個藍色需要一些討論，藍色的不一定是 \((i,i+1)\) 這條邊，可以是 \([1,i]\) 中的某個點覆蓋過去的，但是我們不能只記錄是否覆蓋到 \(i+1\)，可能其可以覆蓋得更遠，為我們之后服務。所以直接 DP 的做法是就是記 \(f_{i,j}\) 表示前綴 SCC 包含了 \([1,i]\)，最遠覆蓋到了 \(j\) 的最小代價。
DP 的約束就是第二維要大于第一維。
暴力轉移的時間復雜度是 \(O(n^4)\) 的，如果進行一些分類討論可以做到 \(O(n^2)\) 的。
但是這個做法還是太復雜了，這里有一個線性做法，就是我們直接記錄第二維度還是太麻煩了。
考慮找到一個極大的轉移區間進行轉移，第一個前綴 SCC 覆蓋 \([1,i]\) 之后，恰好可以連接到 \(i+1\)。
按照這個方式連邊就可以做到線性 DP 了。其中綠筆部分為中點的時候最優。設 \(f_i\) 表示前綴 \([1,i]\) 為一個 SCC 且和 \(i+1\) 有連邊的最小代價，每次暴力枚舉 \(j\) 轉移，時間復雜度 \(O(n^2)\)。
CF889E Mod Mod Mod
第一次見到這種轉移的 DP。本題我們只記錄當前最優，剩下的遞歸到后面轉移。
首先注意到只有前綴最小值的 \(a_i\) 才有用，保留這些關鍵序列即可，記為 \(\{b_i\}\)。設 \(pre_i\) 表示 \(b_i\) 以及它之前包括被刪的數有多少數字。
倒著 DP，設 \(f_i\) 表示將前 \(i\) 個 \(b\) 都改成 \(b_i\) 的最優答案。假設在 \(b_{i+1}\) 處我們選擇了 \(x_2\)，在 \(b_i\) 處選擇了 \(x_1\)，肯定是希望最大化 \(x_1\)，當 \(x_1<b_{i+1}\bmod b_i\) 的時候，\(x_2=\lfloor\dfrac{b_i}{b_{i+1}}\rfloor b_{i+1}+x_1\)，當 \(x_1\ge b_{i+1}\bmod b_i\)，\(x_2=(\lfloor\dfrac{b_i}{b_{i+1}}\rfloor-1) b_{i+1}+x_1\)。
第二種轉移是可以直接做的，因為不管 \(x_1\) 取什么值，這個轉移都是合法的， \(dp_i\gets dp_i+pre_i(\lfloor\dfrac{b_i}{b_{i+1}}\rfloor-1) b_{i+1}\)。
第一種轉移很難做，因為我們并不知道 \(dp_i\) 中的 \(x_1\) 取值。這個時候我們可以直接往前遞歸，找到一個最小的 \(j\)，滿足 \(b_j\le b_{i+1}\bmod b_i\)，按照上述討論繼續轉移即可。由于每次取模大小會減少至少一半，所以我們單次只會轉移 \(O(\log V)\) 次。
時間復雜度 \(O(n\log n\log V)\)。
P6891 [JOISC2020] ビルの飾り付け 4
首先 \(O(n^2)\) 的 \(dp_{i,j,0/1}\) 是顯然的。
CF1444E Finding the Vertex
P5912 [POI2004] JAS
Uninity
貌似這種交互庫動態構造的題目都是要先用 \(dp\) 求出最優詢問策略。
詢問 \((u,v)\)，根據回答，在 \(u/v\) 的子樹中尋找。尋這個過程就是一個邊分治的過程。我們需要最小化邊分樹每條邊的深度。當邊深度滿足條件的時候，邊分樹和邊深度集是雙射的。需要滿足的條件就是對于任意兩條權值相等的邊，他們公共祖先的邊需要有邊權值小于他們。
浙公網安備 33010602011771號