人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

Educational DP Contest:B - Frog 2

問題

atcoder.jp

解法

dp(i) := 足場 i に行くまでにかかるコストの最小値

と定義する.このとき,

dp(i) = min( dp(i - j) + | h_i - h_(i - j) | ) (1 <= j <= K)

と漸化式が立つ.状態数 O(N),遷移 O(K) となり O(NK).

解答

atcoder.jp

f:id:babcs2035:20190107163827p:plain