2014春合宿2-3 Collecting Stamps 解説

問題リンク

解説

どのような移動が可能か考えると，「上り路線から，ある駅で下り路線に変えていくらか戻ったりスタンプを押したりして，またどこかの駅で上り路線に乗り直す」という動きの連鎖になることがわかる． 次のような DP ができる．

$dp[i][j]=i$ 番目までで，$j$ 回下りから上りへの乗り換えをしたときの移動距離の合計

ここで，下りから上りへの乗り換えを先にしておくのと，乗り換えでぐるぐる回るぶんの移動距離を遷移に組み込めるのがポイントになる．

同じ駅で複数回乗り換えできるので愚直にやると $O(N^3)$ になるが，同じ $i$ の中で遷移させてまとめると，$O(N^2)$ に落ちる．