题目的意思就是可以交换差分数组，对答案进行化简：n∑ai2−(∑ai)2 ，再通过手玩分析可得最优解的差分数组一定是单谷（可以感性理解一下），因此我们将差分数组排序，依次加入，每次可以选择加在左边或者右边，转移方程就可以写出来了。
为了将空间优化，可以用滚动数组。
1 #include <bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 const int N = 1e4 + 10, M = 6e6 + 10, inf = 1e18;
5 int n, a[N], b[N], sum[N], f[2][M], cnt, ans = inf;
6
7 signed main () {
8 scanf("%d", &n);
9 for (int i = 1; i <= n; i++) cin >> a[i];
10 for (int i = 1; i < n; i++) b[i] = a[i + 1] - a[i];//差分数组
11 sort(b + 1, b + n);
12 for (int i = 1; i < n; i++) if (b[i] == 0) cnt++;//为0的不用管
13 for (int i = 1; i < n; i++) sum[i] = sum[i - 1] + b[i];
14 int maxn = a[n];
15 for (int i = 1; i <= maxn * n; i++) f[cnt & 1][i] = inf;
16 for (int i = cnt + 1; i < n; i++) {
17 for (int j = 0; j <= maxn * n; j++) f[i & 1][j] = inf;
18 for (int j = 0; j <= maxn * n; j++) {
19 if (f[(i & 1) ^ 1][j] == inf) continue;
20 //刷表法
21 f[i & 1][j + sum[i]] = min(f[i & 1][j + sum[i]], f[(i & 1) ^ 1][j] + sum[i] * sum[i]);//放右边
22 f[i & 1][j + b[i] * i] = min(f[i & 1][j + b[i] * i],f[(i & 1) ^ 1][j] + 2 * j * b[i] + b[i] * b[i] * i);//放左边
23 }
24 }
25 for (int i = 0; i <= maxn * n; i++)//统计答案
26 if(f[(n & 1) ^ 1][i] != inf) ans = min(ans, n * f[(n & 1) ^ 1][i] - i * i);
27 cout << ans <<endl;
28 return 0;
29 }
