yukicoder No.496 ワープクリスタル (給料日前編)
解法
dpします. どんなdpかというと,
です. まずこのdpテーブルにまで徒歩でいったときのコストを入れておきます.
このdpテーブルに対し, ワープクリスタルを１つずつ使っていき, コストが小さくなる部分を小さくしていきます.
具体的には
をすべてのワープクリスタルに対して検査すればが答えです.
しかし, 同じワープクリスタルは二度使えないため, ゴールから更新していくか, 別の配列に結果を一時保存しておいてあとでまとめて更新するかのどちらかが必要です. (これをせずに順次スタート地点から更新すると, 更新された地点を経由する路で再びワープクリスタルを用いる可能性がある.)
感想
ナップザック風です.
