2015JOI予選4 シルクロード 解説

問題リンク

解説

基本的な動的計画法の問題です。

を、 日目に 番目の都市にいるときの、そこまでの疲労度の最小値とします。 疲労度は場所と日付がわかれば計算でき、次の都市にしか遷移しないので、このDPは で遷移し、時間計算量は となります。

出題当時は、この問題を解いて、残りの部分点を取ることで予選を通過できましたが、5年経過した現在、本選出場のボーダーラインはさらに難しくなっています。このような問題は、ボーダーラインの問題を解きにいくための通過点となる可能性が高いです。予選の時には素早く解けることが望ましいです。