[AtCoder] DP Contest

前言

最早到最晚 submission 差了快兩個月，可見我有多懶 基本上這個 DP 題單還不錯，包含了一大部分的 DP， 下面我會列出一些比較難的題目， 主要是些給自己看，也順便看看有沒有幫忙到卡題的人。

題解

題單連結 Link

J - Sushi

觀察

  • 盤子的分布是無序的

這樣下來只要記錄 1 個的有幾盤，2 個的有幾盤，3 個的有幾盤就好， 狀態設為 $dp[i][j][k]$，表示 1 個的有 $i$ 盤，2 個的有 $j$ 盤，3 個的有 $k$ 盤。

但是轉移時要怎麼辦？

性質

每步有成功吃掉的機率為 $p = \frac{i + j + k}{N}$， 所以，遇到有成功吃掉需要的期望步數：

$$ \begin{align*} E & = p\sum_{n = 0}^{\infty}(n+1)(1-p)^n \\ & = p\sum_{n = 0}^{\infty}n(1-p)^n + p\sum_{n = 0}^{\infty}(1-p)^n \\ & = p\sum_{n = 0}^{\infty}n(1-p)^n + \frac{p}{1-(1-p)} \\ & = p\sum_{n = 0}^{\infty}n(1-p)^n + 1 \\ & = p\sum_{\color{yellowgreen}{n = 1}}^{\infty}n(1-p)^n + 1 \\ & = (1-p)p\sum_{n = 1}^{\infty}n(1-p)^{n - 1} + 1 \\ & = (1-p)p\sum_{\color{yellowgreen}{n = 0}}^{\infty}(n+1)(1-p)^n + 1 \\ & = (1-p)E + 1 \\ pE & = 1 \\ E & = \frac 1 p \\ \end{align*} $$

這樣轉移時所加的步數就分別乘上 $\frac{N}{i + j + k}$ 就好。

T - Permutaion

觀察

  • 實際上，只有剩下的元素 + 最後一個會對放法做出限制。

要怎麼設狀態？

做法

既然只跟大小關係有關， 那可以設狀態為 $dp[i][j]$ 表示現在要考慮第 $i$ 個， 其中放好的最後一個（$i - 1$）是剩下的裡面第 $j$ 大的， 轉移的時候，

  • 如果是 >，表示我上一次只能選的前 $N - i + 1$ 到 $j + 1$ 個元素，
  • 如果是 <，表示我上一次只能選的前 $j$ 到 $1$ 個元素作為下一次的可能，

所以轉移就是：

$$ \begin{cases} \displaystyle dp[i][j] = \sum_{k = j+1}^{N-i+1} dp[i - 1][k] & s[i - 1] = \texttt{>} \\ \displaystyle dp[i][j] = \sum_{k = 1}^{j} dp[i - 1][k] & s[i - 1] = \texttt{<} \\ \end{cases} $$

在這裡使用前綴和可以做到 $\mathcal{O}(N^2)$。

U - Grouping

觀察

  • 枚舉集合？

方法是設 $dp[S]$ 表示這個集合 $S$ 的最大值，可以用 bitmask 表示， 所以 $dp[S] = \max_{T \in S}dp[T] + dp[S \setminus T]$。

但是要怎麼有效率的枚舉？

性質

考慮 $S$ 的所有子集， 剛好會有 $2^{|S|}$ 個， 要怎麼一一枚舉？有個很簡單的寫法：

1
2
3
4
5
6
7

for (int i = 1; i < (1LL << N); i++)
        for (int j = i;; j = ((j - 1) & i))
        {
            //do something...
            if (j == 0)
                break;
        }

為什麼這樣寫是好的？ 當我把 j 減 1 的時候， 會把最低位元改成後綴的 1，再取跟 i 有交集的部分， 就可以依序枚舉所有子集了。

但是直接算的時候複雜度 $\mathcal{O}(N^23^N)$， 所以可以預先處理子集的和，得到複雜度 $\mathcal{O}(N^22^N+3^N)$。

V - Subtree

觀察

  • 如果只要求 $1$ 號點當根？ 直接樹 DP 下去。
  • 但題目要求所有點當根，要怎麼做？

做法

當我要計算某個點的時候，其實只缺他父節點的那條邊的 DP 值， 由於算 DP 的時候是用 DFS 下去的， 其實可以多開一個陣列紀錄答案， 在第 2 次 DFS 下去的時候把答案紀錄好，並且把自己的 DP 值暫時替換掉。

而替換掉的值其實就是對於他父節點的所有子樹除了他本身的乘積， 然而這題的模數不一定存在模逆元，所以我們必須處理這個問題， 方法其實跟前綴和很像，只要維護前綴跟後綴乘積就好。

W - Intervals

觀察

  • 要怎麼列狀態才會保證每個線段都只被轉移一次？

也就是說，我需要知道轉移的時候上一個 $1$ 在哪裡，好計算有沒有多蓋到的區間。 所有多蓋到的區間，可以列出轉移式：

$$ dp[i] = \max_{j < i} dp[j] + \sum \{S \mid j < l \leq i \leq r\} $$

觀察一下，一個區間 $[L, R]$ 會被取到的時候， 出現在 $dp[0] \sim dp[L - 1]$ 轉移到 $dp[L] \sim dp[R]$ 的時候， 也就是說，其實是兩次的區間加值， 分別出現在要開始計算 $dp[L]$ 之前跟計算 $dp[R]$ 之後。

做法

應該不難想到，可以用線段樹達到 $\mathcal{O}(N\log N)$ 的時間完成。

X - Tower

觀察

觀察完之後，我們可以列出狀態： $dp[i]$ 表示總重是 $i$ 時的最大價值。 這樣就可以一直枚舉重量看看可不可以放到下面。

但是用什麼順序做可以達到這個目的？

性質

當兩個方塊 $A,\,B$ 要比較的時候， $A$要放在先考慮如果$s_A - w_B < s_B - w_A$。

證明：
當 $A$ 放在 $B$ 前面的時候， $B$ 的剩餘耐重是 $s_B - w_A$， 當 $B$ 放在 $A$ 前面的時候， $A$ 的剩餘耐重是 $s_A - w_B$， 所以，如果前面已經累積了 $W$ 的重量， $A,\,B$ 兩個人先考慮耐重低，再考慮耐重高會是比較好的選擇。

Y - Grid 2

觀察

每一條不合法的路線都一定會至少會撞到一個牆。 且撞到的牆一定是一個合法的 LIS。

做法

先 sort 一次牆座標， 令 $dp[i]$ 表示第一次撞到第 $i$ 個牆，停在第 $i$ 個牆的方法數， 為了方便表示，令 $F(x, y) = C^{x + y}_{x}$， 這樣答案就是

\[ F(H - 1, W - 1) - \sum_{i = 1}^{N} F(H - x_i, W - y_i) dp[i] \]

接著是計算 $dp[i]$，

$$dp[i] = \text{所有組合} - \text{開頭不是}~i~\text{的路徑}，$$

就是

$$\displaystyle dp[i] = F(x_i - 1, y_i - 1) - \sum_{j = 1}^{N} F(x_i - x_j, y_i - y_j) dp[j]$$

這樣不會計算到重覆組合嗎？答案是不會， 原因是因為 $F(x_i - x_j, y_i - y_j)dp[j]$ 的意義是路徑為 $j\rightarrow \cdots \rightarrow i$ 的路徑， 所以不會重複。

另外有一個小細節是，求解跟轉移是一樣的， 所以可以多加一個點 $(H, W)$，直接輸出他的DP值。

Z - Frog 3

性質

轉移式可以化簡：

$$ \begin{align*} dp[i] & = \min_{j < i} \{ dp[j] + (h_j - h_i)^2 + C\} \\ & = \min_{j < i} \{ dp[j] + h_i^2 - 2h_ih_j + h_j^2 + C \} \\ & = \min_{j < i} \{ dp[j] - 2h_ih_j + h_j^2 \} + h_i^2 + C \\ dp[i] & = \min_{j < i} \{(-2h_j) \, h_i + (dp[j] + h_j^2) \} + h_i^2 + C \end{align*} $$

也就是說，他是一條直線。

做法

李超線段樹或者動態凸包都可以，順便恭喜你寫完這份題單了（如果你沒有跳題）。