RT。 代码如下，正常的dp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define upd(x, y) (x = min(x, y))
const int M = 10100, N = 6000, inf = 1e17;
int n, f[M * N], a[M], d[M], s[M], mx = 0, ans = 0xfffffff, sum = 0;

signed main()
{
    // freopen("kout", "w", stdout);
    scanf("%lld%lld", &n, a + 1), fill(f, f + M * N, inf);
    for (int i = 2; i <= n; i++) scanf("%lld", a + i), d[i - 1] = a[i] - a[i - 1], sum += a[i];
    sort(d + 1, d + n), f[0] = 0;
    for (int i = 1; i < n; i++) s[i] = s[i - 1] + d[i];
    // for (int i = 1; i < n; i++) printf("%d %d\n", d[i], s[i]);
    for (int i = 1; i < n; i++)
    {
        if (!d[i]) continue;
        for (int j = mx; j >= 0; j--)
        {
            if (f[j] == inf) continue;
            upd(f[j + i * d[i]], f[j] + i * d[i] * d[i] + 2 * d[i] * j);
            upd(f[j + s[i]], f[j] + s[i] * s[i]);
            mx = max({mx, j + i * d[i], j + s[i]});
            f[j] = inf;
        }
        // printf("%d: %d\n", i, mx);
        // for (int j = 0; j <= mx; j++) (f[j] == inf ? printf("inf ") : printf("%d ", f[j]));
        // printf("\n");
    }
    for (int i = 0; i <= mx; i++)
        if (f[i] != inf) ans = min(ans, n * f[i] - i * i);
    printf("%lld\n", ans);
    return 0;
}