part 1 方差

首先，把这个方差的式子化得优美一些。

我们发现，方差实际上只与平方和和和的平方有关。

part 2 差分

加下来考虑修改操作。

观察后可以发现这个操作的本质就是交换了差分数组上两个相邻的元素。

既然可以任意次交换相邻元素，那么问题转化为已知一个差分数组，求将差分数组重新排列后得到的数列的方差最小是多少。

part 3 动态规划

得到了上面的重要性质，我们先考虑贪心如何解决这个问题。

根据初中知识，如果一列数越接近，那么方差就越小。

由于 $a_1,a_n$ 无法操作，所以考虑让中间的数尽量向中间靠拢。

容易想到尽量让差分值大的排在左右两边，小的放在中间，这样一定最优，例如样例，最优方案 $1,3,4,6$ 的差分是 $2,1,2$，满足该性质。

考虑如果序列 $a$ 中所有元素同时减去一个 $a_1$，方差不变，这样 $a_1$ 就变成了零，方便处理。

如果每次考虑拿最大的放到左右两边，我们发现十分难以通过差分来退出原序列，因此我们考虑从小的往大的放，每次放到当前序列的最前面或者最后面。

设当前的差分数组从小到大排序后为 $b_1,b_2...b_{n-1}$。

考虑到平方和难以统计，所以设 $f_{i,j}$ 表示已经放了 $b_1,b_2...b_i$ 这些元素，当前推出的 $a$ 数组的和为 $j$ ，$a$ 的最小平方和。

当前已经放好的序列是 $b'_1,b'_2...b'_i$，考虑放入 $b'_{i+1}$。

如果放在最后，那么 $a$ 的和加上 $\sum_{i=1}^{i+1} b'_i$。

平方和加上 $(\sum_{i=1}^{i+1} b'_i)^2$。

如果放在最前面，假设已经得到的 $a$ 为

对于和来说，每个数都加了 $b'_{i+1}$，且向后移动一格， $a'_1=b'_{i+1}$，所以和加上了 $(i+1)\times b'_{i+1}$。

平方和加上了：

注意此时复杂度为 $O(n^2\times maxa_i)$，后面的点会爆炸。

考虑如果差分为零，显然直接放中间，可以不进行转移。

时间复杂度 $O(n\times maxa_i^2)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
void getmin(int &x,int y){x=x<y?x:y;}
const int N=1e4+5;
int n,a[N],b[N],tot,maxS,f[2][N*55],s[N];
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<n;i++)b[i]=a[i+1]-a[i];
	n--;
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)if(b[i]==0)tot++;
	for(int i=1;i<=n;i++)s[i]=s[i-1]+b[i];
	maxS=a[n]*n;
	memset(f,63,sizeof(f));
	f[0][0]=0;
	int z=0;
	for(int i=tot;i<n;i++,z^=1){
		for(int j=0;j<=maxS;j++)f[z^1][j]=1e9+7;
		for(int j=0;j<=maxS;j++){
			if(f[z][j]>1e9)continue;
			getmin(f[z^1][j+(i+1)*b[i+1]],f[z][j]+(i+1)*b[i+1]*b[i+1]+2*j*b[i+1]);
			getmin(f[z^1][j+s[i+1]],f[z][j]+s[i+1]*s[i+1]);
		}
	}
	int ans=1e9;
	for(int i=0;i<=maxS;i++)getmin(ans,f[z][i]*(n+1)-i*i);
	printf("%lld",ans);
}