<style> .reveal .slides { text-align: left; font-size:30px; } </style> # DP (單調隊列、區間DP) Introduction to Competitive Programming 06/19 --- - 單調隊列 - 區間 DP - DP 題解 --- ## 單調隊列優化 [例題](https://zerojudge.tw/ShowProblem?problemid=c528)： 給定一整數陣列，求取出數字的總和最大，且滿足相鄰兩數距離不能超過 $k$ ---- 定義狀態： $$dp[i]=\mbox{從頭開始選到 $i$ 且有選 $i$ 的最大值}$$ 狀態轉移： $$dp[i] = arr[i] + max\{dp[i-1], dp[i-2], \dots, dp[i-k+1], 0\}$$ ---- 直接轉: $$O(N*K)$$ 也太大 ---- 觀察一下，還記得 $O(NlogN)$ LIS 嗎?  ---- 類似的想法(其實是一模一樣)，留越左越大的就好了。 你看 $dp[j]$ 如果可以貢獻給 $dp[i] \ 那 \ dp[r] \ (r > j) \ 且 \ dp[r] > dp[j]$ 對於後面的狀態，也就是 $dp[i'] \ (i' > i)$，$dp[j]$ 能貢獻到的，$dp[r]$ 都能貢獻到，所以 $dp[j]$ 可以拔掉，我們留 $dp[r]$ 就好。 所以 $dp[r]$ 大且 $r$ 較大的可以留下。 因此能維護一個 dp 值對 index 單調遞減的序列。 ---- 範例 code (std::deque 很肥最好用其它東西代替) 老慢了 Money 每次砸每次 TLE。 ```cpp= #define pp pair<int,int> #define ss second #define ff first vector<pp> deq(n + 5); int l = 0, r = 0; // l 就是尾巴，r 就是頭。 deq[l] = {0, 0}; // first 存 dp 值，second 存 index for (int i = 1; i <= n; i++) { while (deq[l].ss < i - k) l++; // index 超過轉移範圍的拔光 dp[i] = deq[l].ff + arr[i]; while (l <= r and deq[r].ff <= dp[i]) r--; // index 比隊中的大，且值大所以右邊拔。 deq[++r] = {dp[i], i} } ``` ---- ## 區間DP - 區間 $dp$ 就是定義 $dp[l][r]=$ $l\sim r$ 的最優解。 - 問題會有合併這個動作，所以子結構會被分成 $l\sim k$ 和 $k+1\sim r$。 - 通常會是 $O(n^2)$ 的狀態加上 $O(n)$ 轉移 常見的範圍：$n \le 200, 300, 500$ ---- 矩陣鏈乘積： $r\times h$ 的矩陣乘 $h \times c$ 的矩陣需要 $r\times c\times h$ 次的純量乘法運算。現在有 $n$ 個矩陣 $A_1A_2\cdots A_n$ 要相乘，求最少需要幾次運算 - $A_i$ 是 $r_i \times c_i$ 的矩陣，且 $c_i=r_{i+1},i=1\sim n-1$ $((A_1(A_2A_3))A_4)$ $((A_1A_2)(A_3A_4))$ $(((A_1A_2)A_3)A_4)$ $\cdots$ ---- $dp[l][r]=$ 計算 $A_lA_{l+1}...A_{r-1}A_{r}$ 的最少運算次數 $dp[1][5]$ 的子問題： $(A_1)(A_2A_3A_4A_5) \implies (dp[1][1])(dp[2][5])$ $(A_1A_2)(A_3A_4A_5) \implies (dp[1][2])(dp[3][5])$ $(A_1A_2A_3)(A_4A_5) \implies (dp[1][3])(dp[4][5])$ $(A_1A_2A_3A_4)(A_5) \implies (dp[1][4])(dp[5][5])$ ---- 轉移式：$$dp[l][r] = \min_{k=l\sim r-1}\{dp[l][k]+n_im_km_r+dp[k+1][r]\}$$ 狀態有 $O(n^2) 個$ ，轉移需要 $O(n)$ ，複雜度是 $O(n^3)$ 按照區間長度由小到大計算 $dp$ ---- code ``` for (int i = 1; i <= n; i++) dp[i][i] = 0 // 區間大小為 1 為 base case for (int len = 2; len <= n; len++) // 由小區間往大開始轉移 for (int l = 1, r = len; r <= n; l++, r++) { dp[l][r] = INF; //初值 for (int k = l; k < r; k++) dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + n[i]*m[k]*n[r]); } return dp[1][n]; ``` ---- [P1880 [NOI1995] 石子合并：](https://www.luogu.com.cn/problem/P1880) 有 $n$ 堆石頭擺成 $\textbf{一圈}$，石頭的數量分別是 $a_1 \sim a_n$ ，每次可以合併相鄰的兩堆石頭，獲得的分數是這堆石頭的個數，問把所有石頭變成一堆的最大得分和最小得分 - $1 \le n \le 100, 0 \le a_i \le 20$ ---- 先考慮更簡單的問題，$n$ 堆石頭擺成 "一排" 的情況 $dp[l][r] =$ 把 $l\sim r$ 合併成一堆的最小分數 在 $l\sim r$ 合併成一堆之前他原本是兩堆，這兩堆一定分別是 $l\sim k$ 堆出來的和 $k+1\sim r$ 堆出來的，所以轉移式是 $$dp[l][r] = \min_{k=l\sim r-1}\{dp[l][k]+dp[k+1][r]+sum[l][k]+sum[k+1][r]\}$$ $$= \min_{k=l\sim r-1}\{dp[l][k]+dp[k+1][r]\}+sum[l][r]$$ 複雜度 $O(n^3)$ ---- 現在考慮原問題，在把一圈石頭合併成一堆之前他是兩堆石頭，這兩堆石頭是怎麼來的？ 以 $n=7$ 為例 如果最優解是由 $1\sim4$ 和 $5\sim7$ 兩堆而來的，那 $dp[1][7]$ 可以計算到它  ---- 可是如果是這樣的話 $dp[1][7]$ 就算不到它了  但是我們可以把原序列 $a_1, a_2, a_3,\cdots ,a_7$，透過旋轉擺成 $a_3, a_4, \cdots a_7, a_1, a_2$，再去算 $dp$ ，這時候 $dp[1][7]$ 就可以從由這兩堆轉移而來 ---- 因為我們不知道最優解長怎樣，所以要把 $a_1, a_2, a_3, a_4, a_5, a_6, a_7$, $a_7, a_1, a_2, a_3, a_4, a_5, a_6$, $a_6, a_7, a_1, a_2, a_3, a_4, a_5$, $\cdots$ 都算一遍然後取最優的那個 $dp[1][7]$， 因為要做 $n$ 次 $dp$ 所以複雜度是 $O(n^4)$ ---- 我們不需要每次旋轉一格然後從算，直接把原序列複製一遍接在後面變成 $a_1, a_2, a_3, a_4, a_5, a_6, a_7,$ $a_1, a_2, a_3, a_4, a_5, a_6, a_7$ 再去算長度為 $2n$ 的 $dp$，最後取 $dp[1][7], dp[2][8], dp[3][9], \cdots, dp[7][13]$ 的最小值，複雜度還是 $O(n^3)$ 這是一個很常見的手法，在很多需要算環狀區間的問題都會用到。 ---- [CF1132F Clear the String](https://codeforces.com/problemset/problem/1132/F) 給一個長度為 $n$ 由 $a\sim z$ 組成的字串 $s$，每次操作可以刪除 $s$ 中有連續相同字元的區間，問最少要幾次操作才能把 $s$ 全部消掉 - $1 \le n=|s| \le 500$ ---- 這種消掉一個區間然後再合併的區間消除問題很常見，它有兩個很重要的性質。 1. 連續一樣的東西一定是一起消掉，沒理由分開消 以這題來說，顯然 2. 最左邊或是最右邊的連通塊一定可以留到最後消 以最左邊為例，先消掉最左邊不會影響它右邊的部分，因為它的左邊沒有東西跟右邊合併，所以把最左邊留下先把右邊的部分消完也不影響答案 ---- - 由 1. 我們可以把原字串連續一樣的部分直接變成 $($什麼字元, 有幾個$)$ - 由 2. 我們可以定義 $dp[l][r]=$ 把 $s[l:r]$ ， 消到剩下(不知道幾個) $s[l]$ 需要多少次操作 ---- 轉移： $s[l:r]$ 消成一堆 $s[l]$ 可以 - 直接把 $s[l+1:r]$ 消掉留下 $s[l]$ $dp[l][r] = dp[l+1][r] + 1$ - $s[l]$ 最後跟 $s[k]$ 合併 $s[l]=s[k]$ 要把 $s[l, k-1]$ 消成 $s[l]$，$s[k:r]$ 消成 $s[k]$ $dp[l][r] = dp[l][k-1] + dp[k][r]$ - $s[l]$ 最後跟 $s[k], s[k_1], s[k_2], \cdots$ 合併？ 不用考慮那麼多，如果跟 $s[k_1], s[k_2]\cdots$ 併會比較好的話，會在把 $s[k:r]$ 變成一堆 $s[k]$ 的時候合併，$dp[k][r]$ 已經幫我們處理好了。 ---- $$dp[l][r]=min(dp[l+1][r]+1, \min_{k=l+1\sim r}\{dp[l][k-1]+dp[k][r]\})$$ 答案是 $dp[1][n]+1$ 因為要再花一次操作把 $s[1]$ 消掉。 複雜度：$O(n^3)$ ---- code ``` for (int i = 1; i <= n; i++) dp[i][i] = 0; for (int len = 2; len <= n; len++) for (int l = 1, r = len; r <= n; l++, r++) { dp[l][r] = 1 + dp[l+1][r]; for (int k = l+1; k <= r; k++) if (S[l] == S[k]) dp[l][r] = min(dp[l][r], dp[l][k-1] + dp[k][r]); } return dp[1][n] + 1; ``` ---- [2020 ICPC 台灣站 pE](https://codeforces.com/gym/102835/problem/E) 給一個由 R, G, B, C, M, Y, K 七種字元組成的字串 $s$ ，每次可以把長度 $\ge m$ 的相同字元的子字串消掉，問能不能把 $s$ 全部消掉。 - $0 < n, m, \le 500$ ---- - 由 1. 先把 $s$ 連續相同的部分合併，變成 $($什麼字元, 有幾個$)$ - 由 2. 定義 $dp[l][r]=$ 能把 $s[l:r]$ 消成 "最多幾個" $s[l]$，或是沒辦法 $0$ 如果能把 $s[l:r]$ 全部消掉的話，把最左邊那塊留到最後，等於 $s[l]$ 的這塊最後可能直接消掉或是跟別人合併，不管是哪種一定是越大越好。 ---- 轉移： $s[l:r]$ 消成一堆 $s[l]$ 可以 - 直接把 $s[l+1:r]$ 消掉留下 $s[l]$ 要判斷 $s[l+1:r]$ 能不能被消掉，也就是 $dp[l+1][r] \ge m$ $dp[l][r] = dp[l][l]$ - $s[l]$ 最後跟 $s[k]$ 合併 $s[l]=s[k]$ 要判斷能不能把 $s[l:k-1]$ 消成 $s[l]$，和 $s[k:r]$ 消成 $s[k]$ 也就是 $dp[l][k-1] > 0\ \mbox{and}\ dp[k][r] > 0$ $dp[l][r] = dp[l][k-1] + dp[k][r]$ - $s[l]$ 最後跟 $s[k], s[k_1], s[k_2], \cdots$ 合併？ 不用考慮那麼多... ---- 跟上一題差不多，直接放code ``` for (int i = 1; i <= n; i++) dp[i][i] = cnt[i]; for (int len = 2; len <= n; len++) for (int l = 1, r = len; r <= n; l++, r++) { if (dp[l+1][r] >= m) dp[l][r] = dp[l][l]; for (int k = l+1; k <= r; k++) if (s[l] == s[k] and dp[l][k-1] and dp[k][r]) dp[l][r] = max(dp[l][r], dp[l][k-1] + dp[k][r]); } return dp[1][n] >= m; ``` --- 前面提單的題解: Couting pI - ECPC2016 pK : [閱讀 + 機率轉移](https://vjudge.net/contest/711384#problem/I) Classic pN - 1004 div2 pF : [觀察 + 滾動](https://vjudge.net/contest/698248#problem/N) bitmask pJ - ABC 364 pG : [Steiner Tree](https://vjudge.net/contest/715073#problem/J) bitmask pK - ABC 321 pG: [窮舉子連同塊](https://vjudge.net/contest/715073#problem/K) ---- [ECPC2016 pK](https://codeforces.com/gym/101147/problem/K) 題意: $N$ 個城市，編號從 $0$~$N-1$, 一開始在 $0$，接下來會隨機前往$0$~$N-1$中的任一城市，當你在城市 $i$ 時，下一個前往的城市為 $j$ 的機率是 $P[i,j]$，其中 $P$ 是一個 $N*N$ 的實數矩陣。 $M$ 張牌，編號 $0$~$M-1$，每抵達一個城市的時候就發一張牌，在城市 $r$ 時發出牌 $s$ 的機率是 $C[r,s]$, $C$ 是一個 $N*M$ 的實數矩陣。 給你一個牌編號序列$K$，指的是根據上面的在城市游走發牌後的發牌結果$(發的第一張牌是K[0], 第二張是K[1] .....)$ 問你在符合這個發牌結果的所有可能中在發完 $q$ 張牌後剛好在城市 $z$ 的機率。 - $1\leq N \leq 20 \ , \ 1\leq M \leq 10 \ , \ 1\leq |K| \leq 15$ - $0\leq < K \ , \ 0 \leq z < N$ ---- 很明顯的，如果我們能知道在發過 $i$ 張牌後在各個城市的機率 ( 假設是個 $N$ 維的實數向量 $v$ )，就能進行轉移，因為我們知道在城市 $r$ 時下個去的城市是 $s$ 的機率為 $P[r,s]$，所以直接乘 $v = P^T * v$ , 但這樣沒有限制到當輪牌是 $K[i]$ 的條件，但這也很簡單既然前面的機率描述是“符合結果下到每個城市分別的機率”,那現在有“符合前 $i$ 張牌下到每個城市分別的機率”,那我們其實只要 $v = K[i] * v$ 就搞定了。 好啦，接下來只要在轉移 $q$ 輪後把 $v[z]$ 抽出來其他歸零，再把剩下走完就結束了。 ---- [1004 div2 pF](https://codeforces.com/contest/2067/problem/F) 題意: 給你一個長度 $n$ 的序列 $a$，依照順序進行以下其中之一的操作:  問你在所有的操作中 ($3^n$種中)，每次操作完使得 $P,Q,R$ 中至少兩個數相等的方法數。 $P,Q,R$ 初始為 $0$。 - $1 \leq n\leq 2*10^5$ - $1 \leq a_i\leq 10^9$ 直觀而言當然就是開 $dp[i][P][Q][R]$ 這種感覺，接下來透過觀察壓狀態。 ---- 觀察1. 因為要至少兩數相等所以在做 $a_i$ 前$P,Q,R$的只有可能會是: $(x,x,x)$ 或 $(x,y,y)$ case 1. 那 $a_i$ 不論是什麼都只會把 $(x,x,x)$ 的狀態送到 $(x,x,x \ xor \ a_i)$， case 2. 若 $a_i = x \ xor \ y$ 則可把 $(x,y,y)$ 送到 $(x,x,y)$ 或 $(y,y,y)$ case 3. 若 $a_i \neq x \ xor \ y$ 則只可把 $(x,y,y)$ 送到 $(x \ xor \ a_i,y,y)$ ---- 觀察2. $P \ xor \ Q \ xor R =$ 到 $a_i$前的前綴 $xor$，我們叫他 $p$。 你會發現 $p$ 會剛好是 $(x,y,y)$ 裡的 $x$，或 $(x,x,x)$ 裡的 $x$。 接下來就能開始轉移了。 ---- 轉移: 對於 $(x,y,y)$ 的狀態我們會需要知道 $x、y$ ，由於 $p = x$ 所以只需要紀錄 $y$，像是$dp[i][y]$ 這種感覺，對於 $(y,y,y)$ 我們也是記在 $dp[i][y]$。 對於 case 3. $a_i \neq x \ xor \ y$ 能做的操作只能是 $(p \ xor \ a_i,y,y)$ 所以$dp[i][y] = dp[i-1][y]$ 對於 case 2. $a_i = x \ xor \ y$ 我們首先要把狀態挑出來，$p=x$所以 $a_i \ xor \ p = y$ 這樣 $dp[i-1][y]=dp[i-1][a_i \ xor \ p]$ 就能轉移到 $dp[i][y]$ 或 $dp[i][x]$。 ---- 最後 case 1. $(y,y,y)$、$p=y$ 非常簡單 $dp[i][y] = dp[i-1][p] * 3$ ---- [ABC 321 pG](https://atcoder.jp/contests/abc321/tasks/abc321_g?lang=en) 題意: 有 $N$ 個電路，每個電路都各自有一些紅色及藍色的接口（可能 $0$ 個），所有電路的接口加起來共有 $M$ 個紅的跟 $M$ 個藍的，且只能一個紅接一個藍（可以電路自己接到自己），問你在隨便連的情況下（總共 $M!$ 種中）形成連通塊個數的期望值。 那我們直接考慮，$\sum(連通塊個數*方法數)$ ---- 拆分: 考慮每個單獨連通塊出現的計數。那是不是所有要考慮的連通塊可能就只有 $2^N$ 種，且各自都可以獨立算（先加起來再乘跟先乘再加起來是一樣的）。 ---- 一個連通塊要怎麼連起來？ 當然就是你把他任意分成兩坨後之間都有連線對吧，所以沒有連起來就是至少分成兩塊！那我們不妨直接窮舉一個子集是整個連起來的 + 一個子集是不一定連起來的，這樣可以解決 $(a,b)$ 、$(b,a)$ 要算一種的case，只要讓不一定連起來的那個子集用數字表示時 $>$ 一定連起來的那個子集用數字表示時，就能解決對稱問題。 ---- 像這樣  紅色是指一定連起來的，黑色是不一定連起來的，此時上下只算一種就不會重複算到了。 ----