记录编号	577537	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2021]方差	最终得分	100
用户昵称	00000	是否通过	通过
代码语言	C++	运行时间	0.187 s
提交时间	2022-11-08 22:27:17	内存使用	2.72 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[20000],d[20000],s;
int ans=0x3f3f3f3f,f[2][500005],sum;
int main(){
	freopen("2021variance.in","r",stdin);
	freopen("2021variance.out","w",stdout);
cin>>n;
for(int q=1;q<=n;q++) cin>>a[q];
for(int q=2;q<=n;q++)
	d[q-1]=a[q]-a[q-1];//1~n-1
a[1]=0;
sort(d+1,d+n);
memset(f,0x3f,sizeof(f)); 
f[0][0]=0;
for(int q=1;q<n;q++)//选q个
{
	s+=d[q];
	sum+=d[q]*q;
	for(int w=sum;w>=0;w--)//和为w
	{
		if(w-s>=0)//放右 
		{
			f[1][w]=min(f[1][w],f[0][w-s]+s*s);
		}
		if(w-d[q]*q>=0)//放左
		{
			f[1][w]=min(f[1][w],f[0][w-d[q]*q]+2*d[q]*(w-d[q]*q)+d[q]*d[q]*q);
		}
	}
	for(int w=sum;w>=0;w--) f[0][w]=f[1][w],f[1][w]=0x3f3f3f3f;
}
for(int w=1;w<=250000;w++)
{
	if(f[0][w]!=0x3f3f3f3f)
	ans=min(ans,n*f[0][w]-w*w);
} 
cout<<ans;
return 0;
}