<style> .reveal .slides { text-align: left; font-size:28px; } </style> # DP and DP-optimize Introduction to Competitive Programming 5/3 --- ## 上課內容 - 單調隊列 * 單調隊列介紹 * 多重背包優化 - 區間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], 0\}$$ ---- ### 方法一： $max\{dp[i-k], \dots, dp[i-3], dp[i-2], dp[i-1]\}$ 相當於求區間最大值，砸線段樹！ 複雜度 $O(N\log N)$ ---- ### 方法二： $max\{dp[i-k], \dots, dp[i-3], dp[i-2], dp[i-1]\}$ 如果 $a < b$ 且 $dp[a] < dp[b]$，那 $dp[a]$ 就再也用不到了 我們將 $(dp[x], x)$ 存入 deque $k = 7$ ，維護 $dp[4] \sim dp[10]$ $[(8, 4), (3, 5), (5, 6), (7, 7), (6, 8), (1, 9), (2, 10)]$ 把沒用的拿掉會變成 $[(8, 4), (7, 7), (6, 8), (2, 10)]$ 讓 deque 保持單調遞減 ---- 現在要計算 $dp[11]$ $dp[11] = 8 + arr[i] = 5$ (假設) 從右邊塞入 $(dp[11], 11)$ 把比 $dp[11]$ 小的 pop 掉 $[(8, 4), (7, 7), (6, 8), (2, 10)]$ -> $[(8, 4), (7, 7), (6, 8), (5, 11)]$ 在求 $dp[12]$ 之前我們檢查 deque 的最左邊的元素離 $12$ 有沒有超過 $k$ 小於 $12 - k$ 的話要 pop 掉 -> $[(7, 7), (6, 8), (5, 11)]$ ---- 複雜度： 轉移只需要 $O(1)$ 取出 deque 的頭部 每個元素最多只會被 push 一次 pop 一次 所以總複雜度是 $O(N)$ ---- 範例 code (std::deque 很肥最好用其它東西代替) ```cpp= vector<pair<int, int>> deq(n + 5); int l = 0, r = 0; deq[l] = {0, 0}; for (int i = 1; i <= n; i++) { while (deq[l].second < i - k) l++; dp[i] = deq[l].first + arr[i]; while (l <= r and deq[r].first <= dp[i]) r--; deq[++r] = {dp[i], i} } ``` ---- ## 單調隊列優化背包問題 有 $N$ 種物品，價值、重量、個數分別是 $v_i, w_i, t_i$ ，和負重 $M$ 的背包，求最大值。 ---- ### 方法一： 把 $t_i$ 個相同物品當成 $t_i$ 不同物品作 $0/1$ 背包 複雜度：$O(M \sum t_i)$ ---- ### 方法二： 其實不需要 $t_i$ 個物品那麼多，假設 $t_i=15=1111_{(2)}$，把 $t_i$個物品分成 四組分別有 $1, 2, 2^2, 2^3$ 個物品，這些物品可以組合成 $0 \sim 15$ 。如果 $t_i$ 不是 $2^p - 1$ ， 我們可以先取 $q$ 個，讓 $t_i - q = 2^p - 1$ ，把 $t_i 分解成 {1, 2, \dots, 2^{p-1}, q}$ 複雜度：$O(M \sum \log t_i)$ ---- ### 方法三： 觀察轉移式 $$dp[i][j] = \max_{k=0\sim t_i}\{ dp[i-1][j-k*w[i]]+k*v[i] \}$$ $$ = \max_{k=0\sim t_i}\{ dp[i-1][j-k*w[i]]-\lfloor\frac{j-k*w[i]}{w[i]}\rfloor*v[i]\}+\lfloor\frac{j}{w[i]}\rfloor * v[i]$$ 我們令 $F[t] = dp[i-1][t] + \lfloor \frac{t}{w[i]} \rfloor*v[i]$，轉移式就可以寫成 $$ dp[i][j] = \max_{k=j, j-w[i],\dots j-w[i]*t[i]}\{F[k]\}+\lfloor \frac{j}{w[i]} \rfloor * v[i] $$ 這樣就可以把 $(F[i], i)$ 丟進 deque 維護單調性 ---- 對每個物品 $i$ ，分別對所有除 $w[i]$ 有相同餘數的 $index$ 做單調隊列優化 DP ，一共做 $w[i]$ 次，複雜度是 $O(MN)$ 。 --- ## 區間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; ``` --- ## 數位 DP 數位是指個、十、百、千等等一位一位地拆開，通常是拆十進位數$(0\sim 9)$或二進位數$(0,1)$ 問在 $[L, R]$ 之間滿足某些條件的數有幾個，$L,R$ 的範圍通常可以到 $10^{18}$ 或是 $2000 \sim 5000$ 位數，條件會跟位數或是數值有關。 ---- [例題1](https://cses.fi/problemset/task/2220)： 給你 $a, b$ 兩個數字，問 $a\sim b$ 沒有連續兩位相同的數有幾個 - $0 \le a \le b \le 10^{18}$ ---- 問題的答案是 $ans_{[L,R]}$，我們可以拆成 $ans_{[0,R]}-ans_{[0,L-1]}$，問題變成求 $0\sim S$ 有幾個滿足條件的數 記 $S[i]$ 表示 $S$ 從左往右看的第 $i$ 位，可以把 $S$ 想像成字串 從最高位開始放數字，現在要放第 $i$ 位，要滿足兩個條件 - 不能跟前一位 $S[i-1]$ 相同 - 不能超過 $S$ 如果前面已經有一位 $j$ 滿足 $x[j] < S[j]$ 後面不管怎麼放都不會超過 $K$，如果前面個位數都跟 $S$ 一樣，那目前要放的這一位不能超過 $S[i]$ ---- 我們需要知道兩個資訊，前面個位數是不是貼著 $S$ 或已經小於 $S$，和前一位數是什麼，所以我們定義 $dp[i][j][0]=$ 第 $i$ 位是 $j$，且前 $i$ 位小於/等於(0/1) $S$ 的前 $i$ 位，且滿足條件的數有幾個 最後的答案是 $\sum dp[|S|-1][0\sim 9][0/1]$ ---- 用 push 的方式轉移 - $dp[i][j][0]$ 已經不用關心大小了，只要和 $j$ 不一樣就好 for $k=0\sim 9 \land k \ne j$ $dp[i+1][k][0] \mathrel{+}= dp[i][j][0]$ - $dp[i][j][1]$ 除了不能跟 $j$ 一樣還不能超過 $S[i+1]$ if $S[i+1] \ne j$ $dp[i+1][S[i+1]][1] \mathrel{+}= dp[i][j][1]$ for $k = 0\sim S[i+1]-1 \land k \ne j$ $dp[i+1][k][0] \mathrel{+}= dp[i][j][1]$ ---- 狀態數： $O(|S|\times 10 \times 2)$ 轉移數：$O(10)$ 複雜度 $O(10\times 10\times 2\times |S|)=O(位數)$ ---- code ``` long long l, r; cin >> l >> r; auto DP = [&](long long x) -> long long { if (x == -1) return 0; vector<int> s; for (char c : to_string(x)) s.emplace_back(c - '0'); const int n = s.size(); memset(dp, 0, sizeof(dp)); for (int i = 1; i <= s[0]; i++) dp[0][i][i == s[0]] = 1; for (int i = 0; i+1 < n; i++) { dp[i][0][0]++; for (int j = 0; j < 10; j++) { for (int k = 0; k < 10; k++) { if (k == j) continue; if (k < s[i+1]) dp[i+1][k][0] += dp[i][j][1]; if (k == s[i+1]) dp[i+1][k][1] += dp[i][j][1]; dp[i+1][k][0] += dp[i][j][0]; } } } long long ans = 1; for (int i = 0; i < 10; i++) ans += dp[n-1][i][0] + dp[n-1][i][1]; return ans; }; cout << DP(r) - DP(l-1) << '\n'; ``` ---- [例題2：](https://atcoder.jp/contests/dp/tasks/dp_s) 計算 $1\sim K$ 中有幾個數滿足以下條件，輸出 $\mbox{mod } 10^9+7$ 後的結果 - 所有位數的總和是 $D$ 的倍數 - $1 \le K < 10^{10000}$ - $1 \le D \le 100$ ---- 這次我們不需要紀錄上一位放什麼，但是要記錄目前的位數和是多少，我們最後只關心他是不是 $D$ 的倍數，所以定義狀態為 $dp[i][j][0] =$ 前 $i$ 位的位數和 $\% D$ 為 $j$，且前 $i$ 位小於/等於(0/1) K 的前 $i$ 位的數有幾個 答案是 $dp[|K|-1][0][0]+dp[|K|-1][0][1]$ ---- 轉移： 這裡一樣用 push 的 - $dp[i][j][0]$ 後面可以放任合數 for $k=1\sim 9:$ $dp[i+1][(j+k)\%D][0] \mathrel{+}= dp[i][j][0]$ - $dp[i][j][1]$ 後面不能放超過 $K[i+1]$ 的數 for $k=1\sim K[i+1]$ $dp[i+1][(j+k)\%D][k==K[i+1]] \mathrel{+}= dp[i][j][1]$ 複雜度：$O(Dlog_{10}K)$ ---- code ``` for (int i = 0; i <= s[0]; i++) dp[0][i%d][i == s[0]] += 1; for (int i = 0; i + 1 < n; i++) { for (int j = 0; j < d; j++) for (int k = 0; k < 10; k++) { if (k <= s[i+1]) (dp[i+1][(j+k)%d][k == s[i+1]] += dp[i][j][1]) %= mod; (dp[i+1][(j+k)%d][0] += dp[i][j][0]) %= mod; } } cout << (dp[n-1][0][0] + dp[n-1][0][1] + mod - 1) % mod << '\n'; ``` --- ### Homework and Practice deadline: 5/13 link: https://vjudge.net/contest/556099