Educational DP Contest / DP まとめコンテスト
Updated:
Educational DP Contest / DP まとめコンテスト
ぼちぼち解いていきます。
Source codes
Solutions
基本は $0$-indexed とする。
A - Frog 1
$DP[i] = i$ 番目に至るコストの総和の最小値
とする。初期状態： $DP[0] = 0$, $DP[i] = \infty$ ( $i \geq 1$ ) 、答え $DP[N - 1]$ である。
遷移は以下の通り。 $i = 0, \dots, N - 2$ に対し、 $j = i + 1, i + 2$ に対し、 $j \leq N - 1$ ならば $DP[j] \gets \min(DP[j], DP[i] + \lvert h _i - h _j \rvert )$ とする。
ポイント
この問題は人をバカにするほどには易しすぎず、しかし難しすぎない、いい問題だと思う。
B - Frog 2
上の解法を $j = i + 1, \dots, \min(N - 1, i + K)$ に変更するだけである。
ポイント
これもいい問題ですね。 A が B の発展形であることが自然にわかる。