ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Educational DP Contest / DP まとめコンテスト Z - Frog 3

問題
提出コード

解法

dp[i] = i番目の足場へ行く最小コスト
とします。すると、
dp[i] = min(dp[j] + (h_{i} - h_{j})^{2} + C) (j \lt i)
となります。
これを式変形すると、
dp[i] = min(dp[j] + h_{j}^{2} - 2h_{i}h_{j}) + h_{j}^{2} + C
となります。h_{j}^{2} + Cは最後に足して問題ないことがわかります。
a_{j} = -2h_{j}, b_{j} =dp[j] + h_{j}^{2} とすると、
dp[i] = min(a_{j}h_{i} + b_{j}) + h_{j}^{2} + C
という式になり、調べたいのは、
a_{j}x + b_{j}x = h_{i}の際の最小値
となります。
これは直線の式になっているので、
たとえばCHT アルゴリズムで検索をすると下のような記事が、

http://satanic0258.hatenablog.com/entry/2016/08/16/181331

また、Li Chao Treeで検索をすると下のような記事が出てきます。

https://smijake3.hatenablog.com/entry/2018/06/16/144548

あとは、これらのアルゴリズムを用いて、

  • h_{i}でクエリを投げる(得られた最小値をxとします)

  • a_{i} = -2h_{i},b_{i} = x + 2h_{i}^{2} + Cの直線を追加する

という操作を繰り返すと、h_{N}のクエリの答えxに、h^{2} + Cを加えたものが答えになります。
h_{1}のみ、クエリを投げずにa_{1} = -2h_{1},b_{1} = h_{1}^{2}の直線を追加します。

感想

上記のアルゴリズム達は、直線を管理するアルゴリズム、ということだけ知っていたので、もしかしてこれかな?と思い検索をかけるとぴったりハマったので嬉しかったです。