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

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

前提知識

• CHTによるDP高速化

解説

https://atcoder.jp/contests/dp/submissions/3956069

以下の解説の前にCHTについてわかっていないと以下は理解できない。
とりあえず、複数の1次関数にxを代入したときの最小値が得られるという理解でもいい。
　
今までのEDPCのFrog問題同様に
dp[i] := 足場iにカエルがいるときのコストの総和の最小値
と定義して、更新していく。
これを貰うDPとして、漸化式を立ててみる。
dp[i] = min{j=0..i-1} ((H[j]-H[i])^2+C+dp[j])
最小値のカッコの中身を変形する。
(H[j]-H[i])^2+C+dp[j]
= H[j]^2 - 2*H[j]*H[i] + H[i]^2 + C + dp[j]
= -2*H[j]*H[i] + (H[j]^2+dp[j]) + (H[i]^2+C)
このように変形でき、これをminに戻すと、
dp[i] = min{j=0..i-1} (　-2*H[j]*H[i] + (H[j]^2+dp[j]) + (H[i]^2+C)　)
= min{j=0..i-1} (　-2*H[j]*H[i] + (H[j]^2+dp[j])　) + (H[i]^2+C)
とかける。ここで、min部分を高速化することでDP更新を最適化することを考える。
minの中身で
aj = -2*H[j], bj=H[j]^2+dp[j]
とおくと、
dp[i] = min{j=0..i-1} (　aj*H[i] + bj　) + (H[i]^2+C)
のようになる。
ここまで変形すると、CHTで高速化できる案件であると気づく。
　
コストが(H[j]-H[i])^2+Cの時点で経験的にCHTが見えるというものある。
h1＜h2＜…＜hNというCHT特有の制約もある。

int N; ll C; ll H[201010];
ll dp[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> C;
    rep(i, 0, N) cin >> H[i];
 
    ConvexHullDynamic cht;
    dp[0] = 0;
    cht.addLine(-2 * H[0], H[0] * H[0] + dp[0]);
 
    rep(i, 1, N) {
        dp[i] = cht.getBest(H[i]) + H[i] * H[i] + C;
        cht.addLine(-2 * H[i], H[i] * H[i] + dp[i]);
    }
 
    cout << dp[N - 1] << endl;
}