Educational DP Contest / DP まとめコンテスト Z - Frog 3
解法
番目の足場へ行く最小コスト
とします。すると、
となります。
これを式変形すると、
となります。は最後に足して問題ないことがわかります。
とすると、
という式になり、調べたいのは、
のの際の最小値
となります。
これは直線の式になっているので、
たとえばCHT アルゴリズム
で検索をすると下のような記事が、
http://satanic0258.hatenablog.com/entry/2016/08/16/181331
また、Li Chao Tree
で検索をすると下のような記事が出てきます。
https://smijake3.hatenablog.com/entry/2018/06/16/144548
あとは、これらのアルゴリズムを用いて、
でクエリを投げる(得られた最小値をとします)
の直線を追加する
という操作を繰り返すと、のクエリの答えに、を加えたものが答えになります。
のみ、クエリを投げずにの直線を追加します。
感想
上記のアルゴリズム達は、直線を管理するアルゴリズム、ということだけ知っていたので、もしかしてこれかな?と思い検索をかけるとぴったりハマったので嬉しかったです。