[NOIP2021] 方差

题目描述

给定长度为 \(n\) 的非严格递增正整数数列 \(1 \le a_1 \le a_2 \le \cdots \le a_n\)。每次可以进行的操作是：任意选择一个正整数 \(1 < i < n\)，将 \(a_i\) 变为 \(a_{i - 1} + a_{i + 1} - a_i\)。求在若干次操作之后，该数列的方差最小值是多少。请输出最小值乘以 \(n^2\) 的结果。

其中方差的定义为：数列中每个数与平均值的差的平方的平均值。更形式化地说，方差的定义为 \(D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2\)，其中 \(\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i\)。

输入格式

输入的第一行包含一个正整数 \(n\)，保证 \(n \le {10}^4\)。

输入的第二行有 \(n\) 个正整数，其中第 \(i\) 个数字表示 \(a_i\) 的值。数据保证 \(1 \le a_1 \le a_2 \le \cdots \le a_n\)。

输出格式

输出仅一行，包含一个非负整数，表示你所求的方差的最小值的 \(n^2\) 倍。

样例 #1

样例输入 #1

4
1 2 4 6

样例输出 #1

52

提示

【样例解释 #1】

对于 \((a_1, a_2, a_3, a_4) = (1, 2, 4, 6)\)，第一次操作得到的数列有 \((1, 3, 4, 6)\)，第二次操作得到的新的数列有 \((1, 3, 5, 6)\)。之后无法得到新的数列。

对于 \((a_1, a_2, a_3, a_4) = (1, 2, 4, 6)\)，平均值为 \(\frac{13}{4}\)，方差为 \(\frac{1}{4}({(1 - \frac{13}{4})}^2 + {(2 - \frac{13}{4})}^2 + {(4 - \frac{13}{4})}^2 + {(6 - \frac{13}{4})}^2) = \frac{59}{16}\)。

对于 \((a_1, a_2, a_3, a_4) = (1, 3, 4, 6)\)，平均值为 \(\frac{7}{2}\)，方差为 \(\frac{1}{4} ({(1 - \frac{7}{2})}^2 + {(3 - \frac{7}{2})}^2 + {(4 - \frac{7}{2})}^2 + {(6 - \frac{7}{2})}^2) = \frac{13}{4}\)。

对于 \((a_1, a_2, a_3, a_4) = (1, 3, 5, 6)\)，平均值为 \(\frac{15}{4}\)，方差为 \(\frac{1}{4} ({(1 - \frac{15}{4})}^2 + {(3 - \frac{15}{4})}^2 + {(5 - \frac{15}{4})}^2 + {(6 - \frac{15}{4})}^2) = \frac{59}{16}\)。

【数据范围】

对于所有的数据，保证 \(1 \le n \le {10}^4\)，\(1 \le a_i \le 600\)。

#include<bits/stdc++.h>
const int maxn=1e4+10;
using namespace std;
int n,a[maxn],x[maxn],f[2][500001],sum[maxn],top,s,ans;


int main()
{
//	freopen("set1.in","r",stdin);
//	freopen("T.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		x[i-1]=i>1?a[i]-a[i-1]:0;
//		cout<<x[i-1]<<endl;
	}
	sort(x+1,x+n);
	for(int i=1;i<n;i++) sum[i]=sum[i-1]+x[i];
	memset(f,0x7f,sizeof f);
	f[1][x[1]]=x[1]*x[1];
	top=x[1];
	int temp=0;
	for(int i=1;i<n-1;i++)
	{
		temp^=1;
		top+=x[i+1]*(i+1);
		for(int j=0;j<=top;j++)
		{
			s=j+sum[i+1];
//			cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
//			if(s>top) continue;
			f[temp^1][s]=min(1ll*f[temp^1][s],f[temp][j]+1ll*sum[i+1]*sum[i+1]);
		}
		for(int j=0;j<=top;j++)
		{
			s=j+x[i+1]*(i+1);
//			if(s>top) continue;
			f[temp^1][s]=min(1ll*f[temp^1][s],f[temp][j]+1ll*x[i+1]*x[i+1]*(i+1)+2ll*j*x[i+1]);
		}
		memset(f[temp],0x7f,sizeof f[temp]);
	}
	ans=0x7f7f7f7f;
	for(int i=0;i<=top;i++) 
//		cout<<f[(n-1)&1][i]<<endl;
		ans=min(1ll*ans,1ll*n*f[(n-1)&1][i]-1ll*i*i);
			
	cout<<ans<<'\n';
	
	return 0;
}