首先考虑 \(V[X]=E[X^2]-E[X]^2\) ，答案可以化作：
\[n\sum_{i=1}^n a^i - (\sum_{i=1}^n a_i)^2 \]然后观察操作，进行一次操作本质上是交换了差分序列中相邻两个数，也就是说我们可以任意重排这个差分序列。方差的意义实际上是数据的混乱程度，我们可以感性猜测结论：答案必定是差分序列呈:/这样的形状。证明可以感性，把差分序列排序，一个一个往数列里加，那么把当前（也就是最大的那个数）加到序列首或尾一定更优秀（要么所有数一起加一个特别的数，要么只加一个特别大的数，一部分数加一部分数不加只会让数据更加混乱）。
于是按这个思路，给差分数组排序，设 \(f[i][j]\) 表示考虑前 \(i\) 个差分，当前所有 \(a_i\) 的和为 \(j\) 时最小的 \(\sum a_i^2\)，由于每次新的 \(a_i\) 只会加到队首或队尾，可以轻松算出，直接 dp 即可。
发现这样dp复杂度是 \(\Theta(n^2 \max(a))\) 的，我们考虑如果有一个差分为 \(0\)，它一定没有贡献，dp的时候可以跳过，不为 0 的差分只有 \(\max(a)\) 种，所以总复杂度 \(\Theta(n\max(a)^2)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5;
int a[N], n;
ll sum[N], f[2][N * 605];
inline ll min_(ll a, ll b) {
return a < b ? a : b;
}
inline int read() {
register int s = 0;
register char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch & 15), ch = getchar();
return s;
}
int main() {
n = read(); int mx = 0;
for (int i = 1; i <= n; ++i) {
a[i] = read();
mx = mx > a[i] ? mx : a[i];
}
for (int i = 1; i < n; ++i) a[i] = a[i + 1] - a[i];
sort(a + 1, a + n);
sum[0] = 0; int p = 0, q;
for (int j = 1; j <= mx * n; ++j) {
f[0][j] = 1ll * 1e9 * 1e9;
}
for (int i = 1; i < n; ++i) {
sum[i] = sum[i - 1] + a[i];
if (!a[i]) continue;
q = p; p = q ^ 1;
for (int j = 0; j <= mx * n; ++j) {
f[p][j] = 1ll * 1e9 * 1e9;
}
for (int j = 0; j <= mx * n; ++j) {
if (f[q][j] == 1ll * 1e9 * 1e9) continue;
//case1 : put ai in the front
int s = j + i * a[i];
f[p][s] = min_(f[p][s], 1ll * a[i] * a[i] * i + f[q][j] + 2ll * a[i] * j);
//case2 : put ai in the back
s = j + sum[i];
f[p][s] = min_(f[p][s], f[q][j] + 1ll * sum[i] * sum[i]);
}
} ll ans = 1ll * 1e9 * 1e9;
for (int i = 0; i <= mx * n; ++i) {
if (f[p][i] != 1ll * 1e9 * 1e9) {
ans = min_(ans, 1ll * n * f[p][i] - 1ll * i * i);
}
} printf("%lld\n", ans);
return 0;
}