問題

https://atcoder.jp/contests/dp/tasks/dp_z

考え方

ConvexHullTrick を用いる。もらうDPを考えよう。

$dp[i] :=$ 足場 $i\ (0-indexed)$ に至るときの最小のコスト

と定義する。この時DPの遷移は

$dp[i] = min_{0 \le j \le i-1}(\ (h_i - h_j)^2 + C + dp[j])$
$\ \ \ \ \ \ \ \ =min_{0 \le j \le i-1}(\ (-2 h_j * h_i) + (h_j^2 + dp[j]) + (h_i^2 + C))$

となる。 $(-2 h_j * h_i) + (h_j^2 + dp[j])$ の部分は $h_i$ に関する1次関数と捉えることができて $0 \le j \le i-1$ なる $j$ における1次関数たちの最小値は ConvexHullTrick を用いると $O(logN)$ で求めることができる。 $h_i^2 + C$ は定数と考えることができる。