EDPC B - Frog 2
カエル 2
考え方
前問と考え方自体はほぼ同じ。
「$2$ 通りのうち小さい方」が「最大 $K$ 通りの中での最小」に変更となるだけ。
問題は、もらう DP でも配る DP でも、実装方法を少し考えないといけない点。
もらう DP の場合、前問では最初の $2$ つを特別扱いしていた。
しかし、特別扱いする個数が $K$ 個と不確定になってはそうもいかない。
そのため、ループの範囲を max 関数などを使って工夫することになる。
配る DP の場合、大量のダミー足場を付けるなら、いくつ付ければ足りるのか考えなければならない。
また、（今回は影響がないが）メモリや計算時間も確認が必要になる。
あるいは、ダミー足場を用意せずにループをきっちり止めるとしても、止め方を考えなければならない。
いずれにせよ二重ループになるし、範囲外アクセスの慎重な対応が必要で、実装はちょっと大変。
解答に実際の経路まで必要になった場合、バックトレースでまた for ループをブン回すのは大変。
もらう DP で書いて、どこからのルートが採用されたのかもメモしておきたい。
入力例1での動作
入力を受け取る。
n: 5
k: 3
h: {10, 30, 40, 50, 20}dp[i] を、足場 i までの最小コストとする。
コード上では 0-indexed なので、足場 $1$ が dp[0]、足場 $2$ が dp[1] などと対応する。
まず、dp の初期値を用意する。
最小値を求めたいので全て INF で初期化しておき、スタートの足場である dp[0] だけ $0$ にする。
h : {10, 30, 40, 50, 20}
dp: {0, INF, INF, INF, INF}足場 $2$ への最小コストを求める。
足場 $1$ から来る場合だけを考えればよいので、dp[0]+abs(h[0]-h[1]) $= 0+|30-10| = 20$。
よって、dp[1] は $20$ となる。
h : {10, 30, 40, 50, 20}
dp: {0, 20, INF, INF, INF}足場 $3$ への最小コストを求める。
足場 $1$ から来る場合は、dp[0]+abs(h[0]-h[2]) $= 0+|40-10| = 30$。
足場 $2$ から来る場合は、dp[1]+abs(h[1]-h[2]) $= 20+|40-30| = 30$。
小さい方を採用して、dp[2] は $30$ となる。
h : {10, 30, 40, 50, 20}
dp: {0, 20, 30, INF, INF}足場 $4$ への最小コストを求める。
足場 $1$ から来る場合は、dp[0]+abs(h[0]-h[3]) $= 0+|50-10| = 40$。
足場 $2$ から来る場合は、dp[1]+abs(h[1]-h[3]) $= 20+|50-30| = 40$。
足場 $3$ から来る場合は、dp[2]+abs(h[2]-h[3]) $= 30+|50-40| = 40$。
小さい方を採用して、dp[3] は $40$ となる。
h : {10, 30, 40, 50, 20}
dp: {0, 20, 30, 40, INF}足場 $5$ への最小コストを求める。
足場 $2$ から来る場合は、dp[1]+abs(h[1]-h[4]) $= 20+|20-30| = 30$。
足場 $3$ から来る場合は、dp[2]+abs(h[2]-h[4]) $= 30+|20-40| = 50$。
足場 $4$ から来る場合は、dp[3]+abs(h[3]-h[4]) $= 40+|20-50| = 70$。
小さい方を採用して、dp[4] は $30$ となる。
h : {10, 30, 40, 50, 20}
dp: {0, 20, 30, 40, 30}最後の足場の値、つまり dp の最後尾の値が答え。
注意点
特になし。