传送门QAQ

Preface

现在看来当时的我还是太菜了啊QAQ（虽然现在也很菜

Analysis

显然，原序列中每个数都减去同一个数后，方差也不会有任何改变。

为了方便，这里我们先让原式中每个 /(a_i/) 减去 /(a_1/)。

考虑将题中要求的这个式子化简（很简单，过程省去）：

/[n/times /sum_{i=1}^n a_i^2-(/sum_{i=1}^na_i)^2
/]

此时仍然找不到什么思路，因为题中这个操作非常迷惑。

不过观察到，/(a_i /gets a_{i-1}+a_{i+1}-a_i/) 后，/(a_{i-1},a_i,a_{i+1}/) 三项就有了公共项。

考虑差分一下寻找规律。令 /(d_i=a_i – a_{i-1}/)。

发现一次操作后 /(d_i=a_{i+1}-a_i,d_{i+1}=a_i-a_{i-1}/)。

可以发现，一次操作就是交换了 /((d_i,d_{i+1})/) 。那么我们可以通过不断交换随意重排这个序列。

但是这也是有条件的，我们重排是为了让序列的方差最小，这就需要一些处理手段了。

Lemma：满足题意的差分数组必然呈单谷状。

形式化的说，存在一点 /(k(1/le k/le n)/)，满足 /(/forall i /in [1,k),d_i /ge d_{i+1}/) 且 /(/forall i /in [k,n),d_i /le d_{i+1}/)。

感性理解一下，这样构造就是使得 /(a/) 数组中的数值较为集中在平均值附近。

引用一下 这篇题解 的图：

这样构造出来的差分数组长这个样子，那么用前缀和求出原来的 /(a/) 数组就是：

根据初中数学的知识，方差越小，代表着一个序列的「波动」越小，也就是离平均值更近。

显然这样构造是很优秀的，但怎么说明这样就是最优的呢？

证明：

（注：以下均是我从另一篇博客找来的极不严谨较容易理解的方法，严谨的数学证明请看其它博客）

考虑邻项交换。只考虑 /(/ge k/) 的部分，/(/lt k/) 的部分也是同理。

考虑交换 /((d_x,d_{x+1})(x /ge k)/)，显然这只会让原序列中的 /(a_x/) 变大。

但这会导致我们的 /(/bar{a}/) 一起变大，还是不太好判断。

不如回到方差的定义，「波动」越大，方差越大，/(a_x/) 处于较大的一部分，它变大显然会让整个序列的「波动」变大，那么方差也会变大。

（这个解释好牵强QAQ，考场上还是推一推样例找性质，然后打个暴力对拍吧qwq）

有了这个性质，开始设计算法：
将 /(d/) 数组从小到大排序，依次插入新的差分序列的头或尾，显然这样是满足单谷的要求的。

现在要做的是判断是插入序列头还是序列尾部。

状态很多，又是最优化，考虑 DP。

设 /(f(i,j)/) 表示将前 /(d_1/sim d_i/) 插入序列，/(/sum a_i=j/) 时最小的 /(/sum a_i^2/)。

分情况讨论：

• 插入序列头：/(f(i,j) = f(i-1,j – i/times d_i)+ i/times d_i^2+2/times (j-i/times d_i)/times d_i/)。

• 插入序列尾：/(f(i,j)=f(i-1,j-/sum/limits_{k=1}^i d_k)+ j/times j/)。

此时还有一个问题：这个 DP 时空复杂度均为 /(O(N^2/times /max/{a_i/})/)，被数据范围卡住了。

空间可以用滚动数组优化，那时间呢？

观察最后一组数据，/(N/) 非常大，但 /(a_i/) 非常小，说明我们的 /(d/) 数组中存在相当多的 /(0/)。

那么我们遇到 /(0/) 直接跳过就好了。计入时间复杂度的循环就只有 /(O(/max/{a_i/})/) 轮。

此时时间复杂度降到 /(O(N/times /max/{a_i/}^2)/)，可以通过本题。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 5;
const int maxm = 605;
const ll INF = 1e16;
int n,a[maxn],d[maxn],sum[maxn];
ll f[2][maxn * maxm]; 
int main() {
	freopen("variance.in","r",stdin);
	freopen("variance.out","w",stdout);
	scanf("%d",&n);
	int m = n - 1;
	for(int i = 1;i <= n;++ i)scanf("%d",&a[i]);
	for(int i = 1;i <= m;++ i)d[i] = a[i + 1] - a[i];
	sort(d + 1 , d + m + 1);
	for(int i = 1;i <= m;++ i)sum[i] = sum[i - 1] + d[i];
	for(int i = 0;i <= m * sum[m];++ i)f[0][i] = INF;
	f[0][0] = 0;
	bool u = false;
	for(int i = 1;i <= m;++ i) {
		if(!d[i])continue ;
		u ^= true;
		for(int j = 0;j <= sum[m] * m;++ j) {
			f[u][j] = INF;
			if(j >= d[i] * i)f[u][j] = min(f[u][j] , f[u ^ 1][j - i * d[i]] + 1ll * i * d[i] * d[i] + 2ll * (j - i * d[i]) * d[i]);
			if(j >= sum[i])f[u][j] = min(f[u][j] , f[u ^ 1][j - sum[i]] + 1ll * sum[i] * sum[i]);
		}
	}
	ll ans = INF;
	for(int j = 0;j <= m * sum[m];++ j)ans = min(ans , 1ll * n * f[u][j] - 1ll * j * j);
	printf("%lld/n",ans);
	return 0;
}

完结撒花✿✿ヽ(°▽°)ノ✿