Convex Hull Trick
以下の操作を直線の数に対して高速に行うテクニック。
直線の追加
$ xが与えれらたときに、管理している直線のとる$ yの最小値
$ {\rm dp}_i = \min_{j = 0}^{i-1} \{ p(j) q(i) + r(j)\} + s(i)
$ f_j(x) = p(j)x + r(j)としたとき$ \min_{j = 0}^{i-1} \{ f_j(q(i)) \}となっているので
追加する直線の傾きが単調に変わる場合
最小値がほしい$ xも単調に変わる場合
以上の条件がなくても、最小値を調べたい$ xが事前にわかっている場合
参考
わかりやすいスライド
蟻本 p.304