AtCoder DP Round tutorial

--- tags: tutorial --- # AtCoder DP Round tutorial [TOC] ## A. Frog 1 :::spoiler 題解 $dp_i$ 代表只考慮前 $i$ 個石頭時的最佳解 $\begin{align}dp_i=min(&dp_{i-1}+abs(h_{i-1}-h_{i}),\\&dp_{i-2}+abs(h_{i-2}-h_{i}))\end{align}$ 時間複雜度: $\Theta(N)$ [code](https://atcoder.jp/contests/dp/submissions/32702042) ::: ## B. Frog 2 :::spoiler 題解 $dp_i$ 代表只考慮前 $i$ 個石頭時的最佳解轉移式為 $\begin{align}dp_i=min(&dp_{i-1}+abs(h_{i-1}-h_{i}),\\&dp_{i-2}+abs(h_{i-2}-h_{i})\\&...\\&dp_1+abs(h_1-h_i))\end{align}$ 時間複雜度: $\Theta(N^2)$ [code](https://atcoder.jp/contests/dp/submissions/32702042) ::: ## C. Vacation :::spoiler 題解 $ha_i$ 代表第 $i$ 天選 $A$ 的最大幸福度 $hb_i$ 代表第 $i$ 天選 $B$ 的最大幸福度 $hc_i$ 代表第 $i$ 天選 $C$ 的最大幸福度轉移式為 $ha_i = a_i+max(hb_{i-1},hc_{i-1})$ $hb_i = b_i+max(ha_{i-1},hc_{i-1})$ $hc_i = c_i+max(ha_{i-1},hb_{i-1})$ 時間複雜度: $\Theta(N)$ [code](https://atcoder.jp/contests/dp/submissions/32702870) ::: ## D. Knapsack 1 :::spoiler 題解 $dp[i][j]$ 代表考慮前 $i$ 個物品在包包可用空間為 $j$ 時的最大價值轉移式為 $dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]])$ 時間複雜度: $\Theta(NW)$ [code](https://atcoder.jp/contests/dp/submissions/32703198) ::: ## E. Knapsack 2 :::spoiler 題解 與上一題相同但範圍不一樣由於 $W$ 為 $10^9$ 所以用重量DP不太可行這時候可以觀察到 $v_i \leq 10^3$ ，代表總價值不會超過 $N\times 10^3$ 這時候就可以用**考慮前 $i$ 個物品在達到 $j$ 價值時所要花費的最小空間**來DP $dp[i][j]$ 代表考慮前 $i$ 個物品在包包內價值為 $j$ 時所要花費的最小空間轉移式為 $dp[i][j]=min(dp[i-1][j],w[i]+dp[i-1][j-v[i]])$ 記得將 $dp$ 陣列的初始值設成 $inf$ 時間複雜度: $\Theta(N^2max(v_i))$ [code](https://atcoder.jp/contests/dp/submissions/32703411) ::: ## F. LCS :::spoiler 題解 $dp[i][j]$ 代表考慮字串 $s$ 的前 $i$ 個字元和字串 $t$ 的前 $j$ 個字元時的最大長度轉移式為 $dp[i][j]=\begin{cases}1+dp[i-1][j-1] &s[i]=t[j]\\max(dp[i-1][j],dp[i][j-1])&otherwise\end{cases}$ 時間複雜度: $\Theta(|s||t|)$ [code](https://atcoder.jp/contests/dp/submissions/32703728) ::: ## G. Longest Path :::spoiler 題解 注意看題目， $G$ 不包含有向環，代表這是一個**DAG** 在DAG上做DP十之八九都是**拓樸排序**可以解決的問題，這題也不例外經過拓樸排序之後就可以保證**排在後面的節點不會影響到前面的節點**，因此可以遍歷拓樸排序後的節點，利用那些節點的出邊來更新後面的節點虛擬碼 ```= inD[N] // 節點的入度 Vector E[N] // adj_list // 拓樸排序 Queue q for i in range(N): if inD[i] == 0: q.push_back(i) Vector sortedV // 排序過的節點 while size(q) > 0: x = q.front() q.pop_back() for y in E[x]: inD[y] -= 1 if inD[y] == 0: q.push_back(y) sortedV.push_back(x) // DP len[N] // 走到該節點的Longest Path for x in sortedV: for y in E[x]: len[y] = max(len[y], len[x] + 1) // max_element(len) 即為答案 ``` 時間複雜度: $\Theta(N+M)$ [code](https://atcoder.jp/contests/dp/submissions/32704207) ::: ## H. Grid 1 :::spoiler 題解 $dp[i][j]$ 代表從 $(1,1)$ 走到 $(i,j)$ 的走法數轉移式 $dp[i][j]=\begin{cases}0&a[i][j]\ is\ wall\\dp[i-1][j]+dp[i][j-1]&otherwise\end{cases}$ 時間複雜度: $\Theta(NM)$ [code](https://atcoder.jp/contests/dp/submissions/32704356) ::: ## I. Coins :::spoiler 題解 $dp[i][j]$ 代表考慮前 $i$ 個硬幣中有 $j$ 個硬幣是人頭的可能性轉移式對於每個 $dp[i][j]$ ，當 $i<N$ 可以轉移 $dp[i][j]\times p[i]$ 到 $dp[i+1][j+1]$ (此硬幣擲到人頭的情況) 也能轉移 $dp[i][j]\times(1-p[i])$ 到 $dp[i+1][j]$ (此硬幣沒擲到人頭的情況) 時間複雜度: $\Theta(N^2)$ [code](https://atcoder.jp/contests/dp/submissions/32704694) ::: ## J. Sushi :::spoiler 題解 先將吃壽司的方法轉換成數學式用 $dp[a][b][c][d]$ 來表示剩下 $0$ 個壽司的盤子數量有 $a$ 個，剩下 $1$ 個壽司的盤子數量有 $b$ 個 ... 剩下 $3$ 個壽司的盤子數量有 $d$ 個的情況時的期望操作次數可以得到 $\begin{align}dp[a][b][c][d]=&\frac{a}{N}(dp[a][b][c][d]+1)\\+&\frac{b}{N}(dp[a+1][b-1][c][d]+1)\\+&\frac{c}{N}(dp[a][b+1][c-1][d]+1)\\+&\frac{d}{N}(dp[a][b][c+1][d-1]+1)\end{align}$ 移項一下得到 $\begin{align}\frac{N-a}{N}dp[a][b][c][d]=&\frac{a}{N}\\+&\frac{b}{N}(dp[a+1][b-1][c][d]+1)\\+&\frac{c}{N}(dp[a][b+1][c-1][d]+1)\\+&\frac{d}{N}(dp[a][b][c+1][d-1]+1)\end{align}$ 這樣就可以用top-down遞迴的方式去解這題了而因為純遞迴計算會算到許多重複的case，所以需要DP將算過的子問題的答案存起來但由於 $dp$ 這個陣列直接開的話會開到 $300^4$ 這麼大，暴力一點的解法就是拿unordered map裝時間複雜度: $\Theta(N^3)$ 但常數因為unordered map所以頗大 [code](https://atcoder.jp/contests/dp/submissions/32737585) **優化** 可以觀察到其實 $dp[a][b][c][d]$ 裡的 $a,b,c,d$ 相加起來會恆等於 $N$ ，這代表其實只要儲存其中三個數的值就可以得知最後一個數的值因此就可以直接開一個三維的 $dp$ 陣列，不用再用unordered map來存這樣也可顯著的壓低常數時間複雜度: $\Theta(N^3)$ 雖然和優化前一樣但我實際跑起來快了4倍多 [code](https://atcoder.jp/contests/dp/submissions/34510521) ::: ## K. Stones :::spoiler 題解 如果先手選一個 $x$ 能讓後手必輸，那先手就會贏反之如果先手選任何一個 $x$ 都沒辦法讓後手必輸，那先手就會輸設 $dp[i]=true$ 為先手必贏， $dp[i]=false$ 為先手必輸可以得出下列式子 $dp[i]=[[\exists j,j\in A\vee dp[i-j]]]$ 時間複雜度: $\Theta(NK)$ [code](https://atcoder.jp/contests/dp/submissions/32753095) ::: ## L. Deque :::spoiler 題解 當 $N=1$ 的時候，先手的最佳解(也是唯一解)就是拿唯一的那個元素當 $N=2$ 的時候，先手的最佳解是拿比較大的那個元素，這樣的話後手就會拿剩下唯一的那個元素當 $N=3$ 的時候，先手若拿了最前面的元素，後手就可以選擇剩下兩個元素裡面較大的元素，先手就會拿到最後剩下的那個元素，先手拿了最後面的元素的情況亦然。可以發現當 $N=k$ 的時候，先手可以選擇要拿前面還後面，而後手可以拿在剩下範圍的最佳解，於是就可以用陣列的左右界作為狀態來進行DP 轉移式為 $dp[l][r]=max(a[l]+dp[l+1][r],a[r]+dp[l][r-1])$ 要注意DP進行的順序，如果是bottom-up做法的話應該從長度小的區間往上做起時間複雜度: $\Theta(N^2)$ [code](https://atcoder.jp/contests/dp/submissions/32754525) ::: ## M. Candies :::spoiler {state="open"} 題解 待補時間複雜度: $\Theta(NlgN+NK)$ [code](https://atcoder.jp/contests/dp/submissions/32755562) ::: ## N. Slimes :::spoiler 提示 1 每一個進行過合併的 slime ，都是由兩個 slimes 合併而成 ::: :::spoiler 提示 2 一個區間內的 slimes 加總起來的值不管中間如何結合都會一樣 ::: :::spoiler 題解 結合提示1和提示2，可以發現每個區間 $[l,r)$ 的 slimes 結合最小花費都可以從子區間 $[l,k),[k,r)$ 的結合最小花費算出來所以這題可以 bottom-up DP ，從長度 $=1$ 的 case 做到長度 $=N$ 的 case 轉移式為 $dp[l][r]=sum[l][r]+\min\limits_{0\leq k<N}(dp[l][k]+dp[k][r])$ 而 $sum[l][r]$ 可以用前綴和預處理後再 $\Theta(1)$ 的時間算出來時間複雜度: $\Theta(N^3)$ [code](https://atcoder.jp/contests/dp/submissions/32756376) ::: ## O. Matching :::spoiler 題解 要將所有 men 跟 women 配對，我們可以遍歷所有的 men ，對於每個 man ，窮舉所有能配對的 women 。在轉移的過程中，有可能遇到剩下來的 women 組合一樣的情況，所以就可以用 DP 的技巧紀錄這種情況下的可能配對種類。這題看 code 比較好理解， `int c` 是用一個位元來表示一個 woman 有沒有被用過 [code](https://atcoder.jp/contests/dp/submissions/32763963) ::: ## P. Independent Set :::spoiler {state="open"} 題解 待補 [code](https://atcoder.jp/contests/dp/submissions/32766967) ::: ## Q. Flowers :::spoiler 題解 帶權 LIS ，另見 [DDJ a095](http://203.64.191.163/ShowProblem?problemid=a095) 其中一種解法是先將所有高度離散化，再開一個線段樹存區間的最大值(用 treap 的話就可以不用離散化， treap yyds )，由左到右遍歷所有的花，接下來進行以下轉移 $dp[h'[i]]=max(dp[h'[i]],a[i]+\max\limits_{j<h'[i]}(dp[j]))$ 其中 $dp$ 是用來存某個離散化後的高度的最大美麗度的線段樹， $h'$ 則是高度離散化後的對應陣列最後再取線段樹中最大的美麗度即得解 [code](https://atcoder.jp/contests/dp/submissions/34652247) 另一種解是和不帶權的 LIS 比較接近，不過用 map 而不是 vector 來維護該高度上的最大美麗度。在當前花的高度大於先前的所有花時，和不帶權 LIS 一樣，就直接將花加在最後面。否則，二分搜找出可以插入的地方，並且和不帶權 LIS 不同的地方是插入的位置後面如果有更高的位置加總美麗度小於當前高度加總的美麗度，那代表前者已經沒用了，可以用更小的高度達到更高的美麗度。詳見 code [code](https://atcoder.jp/contests/dp/submissions/32767906) ::: ## R. Walk :::spoiler 題解 從 $K\leq10^{18}$ ，可知一定不可能實際走訪 $K$ 步，而可能需要從 $lgK$ 的方向去想，那這題就是可以用倍增法來解決。先來介紹一下倍增法，兩個長度為 $1$ 的路徑，如果第一個路徑的尾和第二個路徑的頭相同，那就可以接起來變成一個長度為 $2$ 的路徑；同理，兩個長度為 $2$ 的路徑接起來可以變成長度為 $4$ 的路徑；兩個長度為 $2^k$ 的路徑接起來變成長度 $2^{k+1}$ 的路徑。我們可以將目標 $K$ 拆解成數個 $2^i$ 長度的路徑相連，這時候再從剛剛建好的倍增表上面查詢，將每一段的路徑總數相乘，就可以求出答案。 [code](https://atcoder.jp/contests/dp/submissions/32771405) ::: ## S. Digit Sum :::spoiler {state="open"} 題解 待補 [code](https://atcoder.jp/contests/dp/submissions/32790963) ::: ## T. Permutation :::spoiler {state="open"} 題解 待補 [code](https://atcoder.jp/contests/dp/submissions/32801519) ::: ## U. Grouping :::spoiler {state="open"} 題解 枚舉子集 DP 待補 [code](https://atcoder.jp/contests/dp/submissions/32803760) ::: ## V. Subtree :::spoiler {state="open"} 題解 樹 DP 待補 [code](https://atcoder.jp/contests/dp/submissions/32805381) ::: ## W. Intervals :::spoiler {state="open"} 題解 資結優化 DP 待補 [code](https://atcoder.jp/contests/dp/submissions/32814094) ::: ## X. Tower :::spoiler {state="open"} 題解 待補 [code](https://atcoder.jp/contests/dp/submissions/32819402) ::: ## Y. Grid 2 :::spoiler {state="open"} 題解 模逆元、數學、DP 待補 [code](https://atcoder.jp/contests/dp/submissions/32820619) ::: ## Z. Frog 3 :::spoiler {state="open"} 題解 斜率優化 DP 、李超線段樹、動態凸包待補 [code](https://atcoder.jp/contests/dp/submissions/32822019) :::