EDPCを解く

EDPCを解いていこう

A - Frog 1

$ \text{dp}[i] $ を足場$i$にたどり着くまでに支払うコストの総和の最小値とする。

\[\text{dp}[i] \leftarrow \min(\text{dp}[i-1]+|h_i-h_{i-1}|,\text{dp}[i-2]+|h_i-h_{i-2}| )\]

で遷移させれば良い。

B - Frog 2

Aと同様に

\[\text{dp}[i] \leftarrow \min_{1\le j\le k}(\text{dp}[i-j]+|h_i-h_{i-j}|)\]

と遷移させる。

C - Vacation

$ \text{dp}[i][j] $ を$i$日目に活動$j$を選ぶときの$i$日目までに得られる幸福度の総和の最大値とする。$i$日目に活動$j$をして得られる幸福度を$a_{ij}$として

\[\text{dp}[i][j]\leftarrow \max_{k\neq j}(dp[i-1][k]+a_{ij})\]

と遷移する。

V - Subtree

$v$を根としたときの、部分木$c$についての答えを$\text{dp}[c]$とする。$v$についての答えは、$v$の子$c$についてその頂点を黒く塗る場合$dp[c]$通り、白く塗る場合$1$通りあるから

\[\text{dp}[v]=\prod_{c\in \text{ch}_v}(\text{dp}[c]+1)\]

となる。これを全方位木DPに載せる。