有名な解法として、convex hull trick (CHT) を用いるものがありますが、それ以外の解法もあります。俗に LARSCH algorithm と呼ばれているものを使います。

状態 \(j\) から \(i\) への遷移コスト \(W(j, i)\) が concave QI と呼ばれる不等式を満たすとき、

\[ E[i] = F[j] + W(j, i) \text{ for } 0\le j<i<n \]

で表される DP を \(O(n)\) 時間で計算できます。ここで、\(E\) がいわゆる DP 配列で、\(F[i]\) は \(E[i]\) から高速に計算できる値（\(F[i] = E[i]\) でも ok）です。

   +--------+
i  | A    B |
   |        |
i' | C    D |
   +--------+
     j    j'

 i     i'    j    j'

 |-----A-----|
       |-----D----|

 |--------B-------|
       |--C--|

この問題での遷移コスト \(W(j, i) = (h_j - h_i)^2+C\) も conave QI を満たすので、このアルゴリズムを使うことができます。

CHT の解法では \((h_j-h_i)^3+C\) や \((h_j-h_i)^4+C\) のようなコストを扱うのはつらそうですが、この解法では問題ありません。

todo: LARSCH algorithm 自体の解説を書く。

実装例：提出 #34087558（あまり洗練されていない）

参考：Larmore, Lawrence L., and Baruch Schieber. “On-line dynamic programming with applications to the prediction of RNA secondary structure.” Journal of Algorithms 12, no. 3 (1991): 490–515.