Squared Ends [CSAcademy #70 E]

https://csacademy.com/contest/round-70/task/squared-ends/

N要素の配列Aがある。
これをKグループに分ける。
各グループ[A[l], A[l+1], ..., A[r]]について(A[l] - A[r])^2のコストがかかる時、コストの総和の最小値は？

前提知識

• 動的CHTによるDP更新高速化

解法

動的CHTはこちらを使っている
　
DPをする。
「DP[k][i] := [0,i]をk個に分ける時のコストの総和最小値」
更新式は
DP[k][i] = min{j=0..i-1} (DP[k-1][j] + (A[i] - A[j+1])^2)
となる。これを展開する。
DP[k][i] = min{j=0..i-1} (DP[k-1][j] + A[i]^2 - 2A[i]A[j+1] + A[j + 1]^2)
= min{j=0..i-1} (-2A[j+1] * A[i] + (DP[k-1][j] + A[j + 1]^2)) + A[i]^2
最小値の部分はax+bの最小値を要求しているので、これはCHTを使って解ける。
普通のCHTではaが単調増加である必要があるので、動的CHTを使ってこれを回避しよう。

int N, K; ll A[10101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];

    vector<ll> dp(N);
    rep(i, 0, N) dp[i] = (A[i] - A[0]) * (A[i] - A[0]);
    rep(k, 1, K) {
        vector<ll> pd(N);
        ConvexHullDynamic cht;
        rep(i, k, N) {
            cht.addLine(-2LL * A[i], dp[i - 1] + A[i] * A[i]);
            pd[i] = cht.getBest(A[i]) + A[i] * A[i];
        }
        swap(dp, pd);
    }

    cout << dp[N - 1] << endl;
}