AtCoder DP Round tutorial

• AtCoder DP Round tutorial
  • A. Frog 1
  • B. Frog 2
  • C. Vacation
  • D. Knapsack 1
  • E. Knapsack 2
  • F. LCS
  • G. Longest Path
  • H. Grid 1
  • I. Coins
  • J. Sushi
  • K. Stones
  • L. Deque
  • M. Candies
  • N. Slimes
  • O. Matching
  • P. Independent Set
  • Q. Flowers
  • R. Walk
  • S. Digit Sum
  • T. Permutation
  • U. Grouping
  • V. Subtree
  • W. Intervals
  • X. Tower
  • Y. Grid 2
  • Z. Frog 3

A. Frog 1

題解

$d{p}_i$ 代表只考慮前

$i$ 個石頭時的最佳解

$\begin{array}{rl}d{p}_i=min(& d{p}_{i-1}+abs(h_{i-1}-h_i),\\ & d{p}_{i-2}+abs(h_{i-2}-h_i))\end{array}$

時間複雜度:

$\mathrm{\Theta }(N)$

code

B. Frog 2

題解

$d{p}_i$ 代表只考慮前

$i$ 個石頭時的最佳解

轉移式為

$\begin{array}{rl}d{p}_i=min(& d{p}_{i-1}+abs(h_{i-1}-h_i),\\ & d{p}_{i-2}+abs(h_{i-2}-h_i)\\ & ...\\ & d{p}_1+abs(h_1-h_i))\end{array}$

時間複雜度:

$\mathrm{\Theta }(N^2)$

code

C. Vacation

題解

$h{a}_i$ 代表第

$i$ 天選

$A$ 的最大幸福度

$h{b}_i$ 代表第

$i$ 天選

$B$ 的最大幸福度

$h{c}_i$ 代表第

$i$ 天選

$C$ 的最大幸福度

轉移式為

$h{a}_i=a_i+max(h{b}_{i-1},h{c}_{i-1})$

$h{b}_i=b_i+max(h{a}_{i-1},h{c}_{i-1})$

$h{c}_i=c_i+max(h{a}_{i-1},h{b}_{i-1})$

時間複雜度:

$\mathrm{\Theta }(N)$

code

D. Knapsack 1

題解

$dp[i][j]$ 代表考慮前

$i$ 個物品在包包可用空間為

$j$ 時的最大價值

轉移式為

$dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]])$

時間複雜度:

$\mathrm{\Theta }(NW)$

code

E. Knapsack 2

題解

與上一題相同但範圍不一樣
由於

$W$ 為

${10}^9$ 所以用重量DP不太可行
這時候可以觀察到

$v_i\le {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$

時間複雜度:

$\mathrm{\Theta }(N^{2}max(v_i))$

code

F. LCS

題解

$dp[i][j]$ 代表考慮字串

$s$ 的前

$i$ 個字元和字串

$t$ 的前

$j$ 個字元時的最大長度

轉移式為

$dp[i][j]=\{\begin{array}{ll}1+dp[i-1][j-1]& s[i]=t[j]\\ max(dp[i-1][j],dp[i][j-1])& otherwise\end{array}$

時間複雜度:

$\mathrm{\Theta }(|s||t|)$

code

G. Longest Path

題解

注意看題目，

$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) 即為答案

時間複雜度:

$\mathrm{\Theta }(N+M)$

code

H. Grid 1

題解

$dp[i][j]$ 代表從

$(1,1)$ 走到

$(i,j)$ 的走法數

轉移式

$dp[i][j]=\{\begin{array}{ll}0& a[i][j]iswall\\ dp[i-1][j]+dp[i][j-1]& otherwise\end{array}$

時間複雜度:

$\mathrm{\Theta }(NM)$

code

I. Coins

題解

$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]$ (此硬幣沒擲到人頭的情況)

時間複雜度:

$\mathrm{\Theta }(N^2)$

code

J. Sushi

題解

先將吃壽司的方法轉換成數學式

用

$dp[a][b][c][d]$ 來表示剩下

$0$ 個壽司的盤子數量有

$a$ 個，剩下

$1$ 個壽司的盤子數量有

$b$ 個 … 剩下

$3$ 個壽司的盤子數量有

$d$ 個的情況時的期望操作次數

可以得到

$\begin{array}{rl}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{array}$

移項一下得到

$\begin{array}{rl}\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{array}$

這樣就可以用top-down遞迴的方式去解這題了
而因為純遞迴計算會算到許多重複的case，所以需要DP將算過的子問題的答案存起來

但由於

$dp$ 這個陣列直接開的話會開到

${300}^4$ 這麼大，暴力一點的解法就是拿unordered map裝

時間複雜度:

$\mathrm{\Theta }(N^3)$ 但常數因為unordered map所以頗大

code

優化

可以觀察到其實

$dp[a][b][c][d]$ 裡的

$a,b,c,d$ 相加起來會恆等於

$N$ ，這代表其實只要儲存其中三個數的值就可以得知最後一個數的值

因此就可以直接開一個三維的

$dp$ 陣列，不用再用unordered map來存
這樣也可顯著的壓低常數

時間複雜度:

$\mathrm{\Theta }(N^3)$ 雖然和優化前一樣但我實際跑起來快了4倍多

code

K. Stones

題解

如果先手選一個

$x$ 能讓後手必輸，那先手就會贏
反之如果先手選任何一個

$x$ 都沒辦法讓後手必輸，那先手就會輸

設

$dp[i]=true$ 為先手必贏，

$dp[i]=false$ 為先手必輸

可以得出下列式子

$dp[i]=[[\mathrm{\exists }j,j\in A\vee dp[i-j]]]$

時間複雜度:

$\mathrm{\Theta }(NK)$

code

L. Deque

題解

當

$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做法的話應該從長度小的區間往上做起

時間複雜度:

$\mathrm{\Theta }(N^2)$

code

M. Candies

題解

待補

時間複雜度:

$\mathrm{\Theta }(NlgN+NK)$

code

N. Slimes

提示 1

每一個進行過合併的 slime ，都是由兩個 slimes 合併而成

提示 2

一個區間內的 slimes 加總起來的值不管中間如何結合都會一樣

題解

結合提示1和提示2，可以發現每個區間

$[l,r)$ 的 slimes 結合最小花費都可以從子區間

$[l,k),[k,r)$ 的結合最小花費算出來

所以這題可以 bottom-up DP ，從長度

$=1$ 的 case 做到 長度

$=N$ 的 case

轉移式為

$dp[l][r]=sum[l][r]+\underset{0\le k<N}{min}(dp[l][k]+dp[k][r])$

而

$sum[l][r]$ 可以用前綴和預處理後再

$\mathrm{\Theta }(1)$ 的時間算出來

時間複雜度:

$\mathrm{\Theta }(N^3)$

code

O. Matching

題解

要將所有 men 跟 women 配對，我們可以遍歷所有的 men ，對於每個 man ，窮舉所有能配對的 women 。
在轉移的過程中，有可能遇到剩下來的 women 組合一樣的情況，所以就可以用 DP 的技巧紀錄這種情況下的可能配對種類。

這題看 code 比較好理解， int c 是用一個位元來表示一個 woman 有沒有被用過

code

P. Independent Set

題解

待補

code

Q. Flowers

題解

帶權 LIS ，另見 DDJ a095

其中一種解法是先將所有高度離散化，再開一個線段樹存區間的最大值(用 treap 的話就可以不用離散化， treap yyds )，由左到右遍歷所有的花，接下來進行以下轉移

$dp[h^{\prime }[i]]=max(dp[h^{\prime }[i]],a[i]+\underset{j<h^{\prime }[i]}{max}(dp[j]))$

其中

$dp$ 是用來存某個離散化後的高度的最大美麗度的線段樹，

$h^{\prime }$ 則是高度離散化後的對應陣列

最後再取線段樹中最大的美麗度即得解

code

另一種解是和不帶權的 LIS 比較接近，不過用 map 而不是 vector 來維護該高度上的最大美麗度。

在當前花的高度大於先前的所有花時，和不帶權 LIS 一樣，就直接將花加在最後面。
否則，二分搜找出可以插入的地方，並且和不帶權 LIS 不同的地方是插入的位置後面如果有更高的位置加總美麗度小於當前高度加總的美麗度，那代表前者已經沒用了，可以用更小的高度達到更高的美麗度。

詳見 code

code

R. Walk

題解

從

$K\le {10}^{18}$ ，可知一定不可能實際走訪

$K$ 步，而可能需要從

$lgK$ 的方向去想，那這題就是可以用倍增法來解決。

先來介紹一下倍增法，兩個長度為

$1$ 的路徑，如果第一個路徑的尾和第二個路徑的頭相同，那就可以接起來變成一個長度為

$2$ 的路徑；同理，兩個長度為

$2$ 的路徑接起來可以變成長度為

$4$ 的路徑；兩個長度為

$2^k$ 的路徑接起來變成長度

$2^{k+1}$ 的路徑。

我們可以將目標

$K$ 拆解成數個

$2^i$ 長度的路徑相連，這時候再從剛剛建好的倍增表上面查詢，將每一段的路徑總數相乘，就可以求出答案。

code

S. Digit Sum

題解

待補

code

T. Permutation

題解

待補

code

U. Grouping

題解

枚舉子集 DP

待補

code

V. Subtree

題解

樹 DP

待補

code

W. Intervals

題解

資結優化 DP

待補

code

X. Tower

題解

待補

code

Y. Grid 2

題解

模逆元、數學、DP

待補

code

Z. Frog 3

題解

斜率優化 DP 、李超線段樹、動態凸包

待補

code