Convex Hull Trick

DPでよく使われるテクニックの1つ。一般に任意の$ xについて高速に$ \min_{j\in S}a_jx+b_jもしくは$ \max_{j\in S}a_jx+b_jを求めたい場合に使う。

以下では簡単のために$ \min_{j\in S}a_jx+b_jだけを考える。この場合は下図のように直線で囲まれた上に凸な凸包を求めたい。

https://gyazo.com/1b8331a01123258f71ab245c3c4b0107

直線が傾きの大きな順番に与えられる場合

たとえばDPで$ dp'_{i} = \min_{1 \le j \le n} \left( dp_j + (h_i - h_j)^2\right)を求めたい場合など。この式は展開すると、

$ dp'_{i} = h_i^2 + \min_{1 \le j \le n} \left( -2h_ih_j + h_j^2 + dp_j \right)

となる。これは式$ y = -2h_jx + h_j^2 + dp_jで表される$ n本の直線群（$ 1 \le j \le n）の凸包の$ x = h_iにおける値を求めることに相当する。

アルゴリズムは以下のようになる。まず直線群を傾きが大きい順にソートしておき、つぎの操作を行いながらデキューに追加していく。

1. デキューのサイズが$ 1以下ならそのまま追加する

2. そうでなければ、最後尾の$ 3本の直線（傾きが一番小さい$ 3本）について以下を計算する。なお、その直線は傾きの大きい順に$ y = a_1x + b_1, \,y=a_2x+b_2, \,y=a_3x+b_3\quad(a_1 \ge a_2 \ge a_3)とする。これが成り立つ場合は、真ん中の直線を削除する。

$ (a_2-a_1)(b_3-b_2)\ge(a_3-a_2)(b_2-b_1)

https://gyazo.com/66b760643c9aed2cfc1b48dd7bfa8f38

デキューが出来たら、各$ iについてつぎの操作を行う

1. デキューから傾きの一番大きい直線をとりだし、その1つ前の直線と$ x = h_iにおける$ yの値を比較する

2. $ yの値が1つ前（自分より1つだけ傾きが小さい直線の$ x=h_iにおける$ yの値）より小さくなるまで 1 をくりかえす

3. いま取り出した直線の$ x = iにおける$ yの値が最小値

4. $ iを1つインクリメントする

このデキューへの操作は全体を通してたかだか$ n回なので各$ h_iにおける$ \left( -2h_ih_j + h_j^2 + dp_j \right)の最小値が計算量$ O(n)で得られる。