一道很厉害的小清新题目

首先我们先把这个式子一通化简：

$$n^2 \times \frac{1}{n} \times \sum_{i=1}^{n} (a_i-\bar{a})^2 $$$$n( \times \sum_{i=1}^{n} a_i^2+\bar{a}^2-2a_i\bar{a} ) $$$$n (\times \sum_{i=1}^{n} a_i^2 + \sum_{i=1}^{n}\bar{a}^2-\sum_{i=1}^{n}2a_i\bar{a}) $$$$n( \times \sum_{i=1}^{n} a_i^2 + n \cdot \bar{a}^2 - 2\bar{a}\sum_{i=1}^{n}a_i ) $$

将 $\bar{a}=\frac{1}{n} \sum_{i=1}^{n} a_i$ 带入得：

$$n \times (\sum_{i=1}^{n} a_i^2 + n \cdot \frac{1}{n^2}{\sum_{i=1}^{n}a_i}^2 - \frac{2}{n}\sum_{i=1}^{n}a_i\sum_{i=1}^{n}a_i ) $$$$n \times (\sum_{i=1}^{n} a_i^2 + n \cdot \frac{1}{n^2}{\sum_{i=1}^{n}a_i}^2 - \frac{2}{n}{\sum_{i=1}^{n}a_i }^2) $$$$n \times (\sum_{i=1}^{n} a_i^2 -\frac{1}{n}{\sum_{i=1}^{n}a_i}^2 ) $$$$n \times \sum_{i=1}^{n} a_i^2 -{\sum_{i=1}^{n}a_i}^2 $$

然后我们可以手玩一下题目中给的操作：

例如有 $a,b,c,d$ 四个数，我们对 $b$ 操作会得到： $a,a+c-b,c,d$

然后我们可以注意到对于每一次操作，相当于交换了两个相邻数的差分

然而我们知道了这个结论如何继续下去呢？

结论就是当方差最小时，差分是先递减后递增呈一个单谷的形状的

可以感性理解一下：首先方差的含义就是一些数据的稳定性，只有在方差呈单谷时稳定性是最好的（可以画图理解）

然后依据这个结论直接dp，看到这里可以自推式子了

首先要把 $d_i$ 排序对叭，然后考虑肯定是从谷底那里开始放，因为已经排完序了

对于一个数 $d_i$ 可以考虑把 $d_i$ 放在谷的左边或者右边

设 $dp_{i,x}$ 表示选了前 $i$ 个，并且当前 $\sum a_i=x$

那么放在左边：

$$dp_{i+1,x+i\times d_i}=\min\{ dp_{i,x}+i\times d_i^2+2\times x\times d_i \} $$

放在右边：

$$dp_{i+1,x+s_i}=\min \{ dp_{i,x}+s_i^2\}$$

其中 $s_i$ 表示 $\sum_{j=1}^{i} d_i$

注意一个小优化，当 $d_i=0$ 时根本不会贡献，所以直接跳过，使用滚动数组

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
bool Test_MLE_start;
constexpr int N=1e6+10;
int _=1,n,nw=0,maxn=0,ans=9e18,a[N],d[N],s[N],dp[2][N];
bool Test_MLE_end;
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c-'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
	//Don't forget!
	memset(dp,0x3f,sizeof(dp));
}
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads();
		for(int i=1;i<=n;i++) a[i]=reads(),d[i-1]=a[i]-a[i-1];dp[nw][0]=0;sort(d+1,d+n);
		for(int i=1;i<n;i++){
			s[i]=s[i-1]+d[i];if(!d[i]) continue; 
			memset(dp[nw^1],0x3f,sizeof(dp[nw^1]));
			for(int j=maxn;j>=0;j--){
				if(dp[nw][j]==inf) continue;
				dp[nw^1][j+i*d[i]]=min(dp[nw^1][j+i*d[i]],dp[nw][j]+i*d[i]*d[i]+2*j*d[i]);
				dp[nw^1][j+s[i]]=min(dp[nw^1][j+s[i]],dp[nw][j]+s[i]*s[i]);maxn=max(maxn,max(j+i*d[i],j+s[i]));
			}nw^=1;
		}for(int i=1;i<=maxn;i++){
			if(dp[nw][i]<inf) ans=min(ans,n*dp[nw][i]-i*i);
		}printf("%lld\n",ans);
	}
	return 0;
}