题解

点个赞拿去抄

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define int long long

using namespace std;

const int N = 1e4 + 5, NA = 5e5 + 5, INF = 0x3f3f3f3f3f3f3f3f;
int n, a[N], d[N], f[NA], g[NA];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) d[i] = a[i + 1] - a[i];
    sort(d + 1, d + n), memset(f + 1, 0x3f, n * a[n] * 8);
    for (int i = upper_bound(d + 1, d + n + 1, 0) - d, sd = 0; i < n; i++) {
        sd += d[i], memcpy(g, f, (n * a[n] + 1) * 8),
            memset(f, 0x3f, (n * a[n] + 1) * 8);
        for (int j = 0; j <= n * a[n]; j++) {
            if (g[j] == INF) continue;
            f[j + i * d[i]] =
                min(f[j + i * d[i]], g[j] + i * d[i] * d[i] + 2 * d[i] * j);
            f[j + sd] = min(f[j + sd], g[j] + sd * sd);
        }
    }
    int ans = INF;
    for (int i = 0; i <= n * a[n]; i++)
        if (f[i] != INF) ans = min(ans, n * f[i] - i * i);
    return cout << ans << endl, 0;
}