[AtCoder] DP Contest

前言

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

題解

題單連結 Link

J - Sushi

觀察

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

但是轉移時要怎麼辦？

性質

每步有成功吃掉的機率為$\displaystyle 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*}$
這樣轉移時所加的步數就分別乘上 $\displaystyle \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] = \text{'>'} \\ \displaystyle dp[i][j] = \sum_{k = 1}^{j} dp[i - 1][k] & s[i - 1] = \text{'<'} \\ \end{cases}$
在這裡使用前綴和可以做到 $\mathcal{O}(N^2)$。

U - Grouping

觀察

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

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

性質

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

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$在哪裡，好計算有沒有多蓋到的區間。
所有多蓋到的區間，可以列出轉移式：
$\displaystyle dp[i] = \max_{j < i} dp[j] + \sum \{S|j < left \leq i \leq right\}$
觀察一下，一個區間$[L..R]$會被取到的時候，
出現在$dp[0]$~$dp[L - 1]$ 轉移到 $dp[L]$~$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}$，
這樣答案就是$\displaystyle F(H - 1, W - 1) - \sum_{i = 1}^{N}F(H - x_i, W - y_i)dp[i] $，

接著是計算$dp[i]$，
$dp[i] = \,所有組合 - 開頭不是i的路徑$，
就是$\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*}$
也就是說，他是一條直線。

做法

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