Educational DP Contest / DP まとめコンテスト A - Frog 1,B - Frog 2

問題(A)
問題(B)
提出コード(B)
Bの問題においてK=2とすればAの問題と同じになります。

解法

個目の足場に行くための最小コスト、とします。すると、
が答えになります。
あとは、

となります。ここで、は1以上以下かつ、が0以上となるような数字です。
今回のDPは、半分全探索をするようなイメージです。
個目の足場に行くには、その~個前の足場からジャンプするしかないです。上の数値で言うとの足場からしか個目の足場へジャンプすることはできません。ということで、足場から、足場までのコストの最小値が全て計算されていたなら、からへ仮に飛んだ場合のコストも求めることができます。これをすべてのに対して計算し、最小値を選べば、足場からまでの最小コストが計算できます。