EDPC B - Frog 2

考え方

前問と考え方自体はほぼ同じ。
「$2$ 通りのうち小さい方」が「最大 $K$ 通りの中での最小」に変更となるだけ。
問題は、もらう DP でも配る DP でも、実装方法を少し考えないといけない点。

もらう DP の場合、前問では最初の $2$ つを特別扱いしていた。
しかし、特別扱いする個数が $K$ 個と不確定になってはそうもいかない。
そのため、ループの範囲を max 関数などを使って工夫することになる。

配る DP の場合、大量のダミー足場を付けるなら、いくつ付ければ足りるのか考えなければならない。
また、（今回は影響がないが）メモリや計算時間も確認が必要になる。
あるいは、ダミー足場を用意せずにループをきっちり止めるとしても、止め方を考えなければならない。

いずれにせよ二重ループになるし、範囲外アクセスの慎重な対応が必要で、実装はちょっと大変。
計算量はどちらでも $O(NK)$ である。

解答に実際の経路まで必要になった場合、バックトレースでまた for ループをブン回すのは大変。
もらう DP で書いて、どこからのルートが採用されたのかもメモしておきたい。

入力例1での動作

入力を受け取る。

n: 5
k: 3
h: {10, 30, 40, 50, 20}

各足場までの最小コストを、前から順に求める。
まだ求めていない足場は、十分大きな値としておく。

最初は足場 $1$ だけを考える。
スタート地点なので、最小コストは $0$ である。

足場 $2$ へは、足場 $1$ から来るしかない。
移動コストは $|30-10|=20$ である。
よって、最小コストは $20$ となる。

足場 $3$ へは、足場 $1,2$ から来られる。
足場 $1$ から来る場合のコストは $0+|40-10|=30$ である。
足場 $2$ から来る場合のコストも $20+|40-30|=30$ である。
よって、最小コストは $30$ となる。

足場 $4$ へは、足場 $1,2,3$ から来られる。
足場 $1$ から来る場合のコストは $0+|50-10|=40$ である。
足場 $2$ から来る場合のコストも $20+|50-30|=40$ である。
足場 $3$ から来る場合のコストも $30+|50-40|=40$ である。
よって、足場 $4$ までの最小コストは $40$ となる。

ここまでの状態は次のようになる。

足場 $5$ へは、$K=3$ なので足場 $2,3,4$ から来られる。
足場 $2$ から来る場合のコストは $20+|20-30|=30$ である。
足場 $3$ から来る場合のコストは $30+|20-40|=50$ である。
足場 $4$ から来る場合のコストは $40+|20-50|=70$ である。

よって、足場 $5$ までの最小コストは $30$ となる。

最後の足場までの最小コスト $30$ が答え。

注意点

特になし。

別解

配る方式

各足場から、そこから $K$ 個先までの足場へ最小コストを配る形でも実装できる。
計算量は同じく $O(NK)$ である。