Atcoder Educational DP Contest 题解

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

01

背包模板题。

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

Atcoder Educational DP Contest 题解

文章操作

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

相关推荐

评论

Atcoder Educational DP Contest 题解