Atcoder Educational DP Contest 题解
Cosmos_zzx
·
·
个人记录
A Frog 1
设 dp_i 为跳到第 i 个台阶的方案数，递推即可。
B Frog 2
发现 1\leq k \leq 100，仿照第一题即可。
C Vacation
设 dp_{i,1/2/3} 表示太郎君在第 i 天做了 A(1) 或 B(2) 或 C(3) 所获得的最大总幸福度，简单递推即可。
D Knapsack 1
## E Knapsack 2
观察到 $1\leq v_i \leq 10^3$，所以将上一题题改成以 $v$ 为下标来做 $dp$，设 $dp_v$ 表示在代价为 $v$ 时的最小重量，最后从大到小遍历一遍统计答案即可。
## F LCS
设 $dp_{i,j}$ 表示 $s$ 字符串前 $i$ 个字符跟 $t$ 字符串前 $j$ 个字符的`LCS`，那么：
$$
dp_{i,j}=\left\{
\begin{aligned}
dp_{i-1,j-1}+1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (s_i=t_j) \\
\max(dp_{i-1,j},dp_{i,j-1})\ \ \ \ \ \ \ (s_i\ne t_j) \\
\end{aligned}
\right.
$$
输出方案直接根据 $dp$ 从后往前推即可。
## G Longest Path
拓扑排序加 $dp$ 即可（最长长度只可能从入度为 $0$ 的点开始）。
## H Grid 1
经典二位表格 $dp$。
## I Coins
从这题开始上升难度了。
设 $dp_{i,j}$ 表示前 $i$ 个硬币有 $j$ 个正面朝上的方案数，根据第 $i$ 个硬币有无朝上来递推即可。
注意 $dp_{i,0}$ 特殊判断。
## J Sushi
> 期望 = 所有可能结果 $×$ 对应概率的加权平均。
$dp[c1][c2][c3] = $ 当前还有 $c1$ 个盘子剩 $1$ 块、$c2$ 个盘子剩 $2$ 块、$c3$ 个盘子剩 $3$ 块时，吃完所有剩余寿司的期望操作次数。
当我们掷一次骰子：
| 掷到的盘子类型 | 概率 | 下一状态 | 说明 |
|---|---|---|---|
| 空盘子 | `(N - c1 - c2 - c3) / N` | 仍是 `(c1, c2, c3)` | 白操作，状态不变 |
| 有 1 块寿司的盘子 | `c1 / N` | `(c1-1, c2, c3)` | 吃完，这个盘子变空 |
| 有 2 块寿司的盘子 | `c2 / N` | `(c1+1, c2-1, c3)` | 吃掉 1 块 → 变成剩 1 块 |
| 有 3 块寿司的盘子 | `c3 / N` | `(c1, c2+1, c3-1)` | 吃掉 1 块 → 变成剩 2 块 |
设：
- $ s = c_1 + c_2 + c_3 $：当前还有寿司的盘子数
- $ E_1 = dp[c_1-1][c_2][c_3] $ **等**是后续状态的期望。
- $E$ 指 $dp[c1][c2][c3]$。
> 期望是对随机变量的“加权平均”。
> 这里的随机变量是“总操作次数”。
> 而总操作次数 $=$ $1$ $+$（后续操作次数）。
> 所以期望也满足：$E[总次数] = 1 + E[后续次数]$。
懂了这些，开始推式子。
$$
E = 1 + \frac{N - s}{N} \cdot E + \frac{c_1}{N} \cdot E_1 + \frac{c_2}{N} \cdot E_2 + \frac{c_3}{N} \cdot E_3
$$
把上面式子中的 $ E $ 项移到左边：
$$
E - \frac{N - s}{N} E = 1 + \frac{c_1}{N} E_1 + \frac{c_2}{N} E_2 + \frac{c_3}{N} E_3
$$
左边变成：
$$
\frac{s}{N} E = 1 + \frac{c_1}{N} E_1 + \frac{c_2}{N} E_2 + \frac{c_3}{N} E_3
$$
两边乘以 $ N $：
$$
s \cdot E = N + c_1 E_1 + c_2 E_2 + c_3 E_3
$$
所以：
$$
E = \frac{N + c_1 E_1 + c_2 E_2 + c_3 E_3}{s}
$$
所以最终转移公式：
$$
dp[c1][c2][c3] = \frac{N + c1 \cdot dp[c1-1][c2][c3] + c2 \cdot dp[c1+1][c2-1][c3] + c3 \cdot dp[c1][c2+1][c3-1]}{c1 + c2 + c3}
$$
看懂这些，这题就好做了。
初始状态：$dp[0][0][0]=0$（没寿司了，不需要操作）。
目标状态：$dp[c1][c2][c3]$（一开始还有 $c1$ 个盘子剩 $1$ 块、$c2$ 个盘子剩 $2$ 块、$c3$ 个盘子剩 $3$ 块）。
因为这题的 $dp[c1+1][c2-1][c3]$ 中有 $c1+1$，$dp[c1][c2+1][c3-1]$ 中有 $c2+1$，按 $c1,c2,c3$ 的顺序会有没用到的状态，所以根据实际情况，选用 $c3,c2,c1$ 的顺序通过此题。
## 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