AOJ0530 Pyon-Pyon River Crossing
解法
DP。
dp[i][j][k] = (k回一行飛ばしのジャンプをして、i行目でj番目の列にいるときの最小の危険度)
とする*1。このとき、
dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][prev][k] + prevからjに移動するときの危険度) (prevはi行目の石のいずれか)
dp[i+2][j][k+1] = min(dp[i+2][j][k+1], dp[i][prev][k] + prevからjに移動するときの危険度) (prevはi行目の石のいずれか)
と配るDPをして更新していけばよい。
ただ、最初と最後は危険度が0で飛ぶことができ、最初と最後にも一行飛ばしをすることができるので、初期化と答えに注意する必要がある。
下の実装では、最初の危険度が0→dp[0][j][0] = 0、最初に一行飛ばし→dp[1][j][1] = 0とし、最後も似た処理を行った。
計算量
O(nmk^2)
コード
感想
- 心がぴょんぴょんする
- わりと素直なDPだけど、実装が少し面倒だった
- AOJのグラフのカテゴリから問題を選んだはずなのだけれども、グラフを使う要素がなかった
- まあグラフに変換して最短距離を求めるという方針も可能かもしれないけれど、その場合は一行飛ばしの回数の処理が難しくなると思う
*1:jは何列目かではなく何番目の列であるかに注意。計算量的には後者の方が小さくなるが、AOJだから後者でもいけるかもしれない
