競技プログラミング用 知識集積所
ABC415E - Hungry Takahashi
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
動的計画法だろうなあ、と気づいた上で、問題はスタートとゴールのどちらから求めるか。
最低金額ギリギリというのはどこかで一度所持金が0になる所持金のことである。
つまり、左上から出発する場合、その範囲ではまだ0になっていないデータを継承しなければならず、大変。
と考えると、バックトレースして右下から出発する方が簡単である。
つまり、左上から出発する場合、その範囲ではまだ0になっていないデータを継承しなければならず、大変。
と考えると、バックトレースして右下から出発する方が簡単である。
これに気付けば「そのマスに入るときにいくらもっていればゴールできるか」を動的計画法で求めるだけ。
なお、各マスは特定の日数にしか突入できないので、食事代をあらかじめ各マスの入手金から引いておくとちょっと楽になる。
