C++(g++ 7.5.0) 解法, 执行用时: 66ms, 内存消耗: 8484K, 提交时间: 2023-07-31 21:03:53

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
	bool f=0;int num=0;char ch=getchar();
	while(!(ch=='-'||(ch<='9'&&ch>='0')))ch=getchar();
	if (ch=='-')f=1;else num=ch-'0';
	while(ch=getchar(),(ch<='9'&&ch>='0'))num=num*10+ch-'0';
	if (f)num=-num;return num;
}
const int inf=1e18;
const int M=1e4+10;
int n,a[M],b[M],sum[M],dp[2][M*55],ans=inf;
signed main()
{
	//freopen("variance.in","r",stdin);
	//freopen("variance.out","w",stdout);
	n=read();
	for (int i=1;i<=n;i++)a[i]=read();
	for (int i=1;i<n;i++)b[i]=a[i+1]-a[i];
	sort(b+1,b+n);int cnt=0;
	for (int i=1;i<n;i++)if (b[i]==0)cnt++;
	for (int i=1;i<n;i++)sum[i]=sum[i-1]+b[i];
	int maxn=a[n];
	for (int i=1;i<=maxn*n;i++)dp[cnt&1][i]=inf;
	for (int i=cnt+1;i<n;i++)
	{
		for (int j=0;j<=maxn*n;j++)dp[i&1][j]=inf;
		for (int j=0;j<=maxn*n;j++)
		{
			if (dp[(i&1)^1][j]==inf)continue;
			dp[i&1][j+sum[i]]=min(dp[i&1][j+sum[i]],dp[(i&1)^1][j]+sum[i]*sum[i]);
			dp[i&1][j+b[i]*i]=min(dp[i&1][j+b[i]*i],dp[(i&1)^1][j]+j*2*b[i]+b[i]*b[i]*i);
		}
	}
	for (int i=0;i<=maxn*(n-1);i++)
		if (dp[(n&1)^1][i]!=inf)ans=min(ans,n*dp[(n&1)^1][i]-i*i);
	cout<<ans<<endl;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 49ms, 内存消耗: 8404K, 提交时间: 2022-10-21 16:38:33

#include<bits/stdc++.h>
using namespace std;

const long long INF=1e18;
const int N=1e4+10;
long long n,a[N],b[N],dp[2][N*55],ans=INF,k;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",a+i);
	for(int i=1;i<n;i++) a[i]=a[i+1]-a[i];
	sort(a+1,a+n);
	int k=0;
	for(long long i=1;i<n;i++) k+=(a[i]==0),b[i]=b[i-1]+a[i];
	for(long long i=1;i<=a[n]*n;i++) dp[k&1][i]=INF;
	for(long long i=k+1;i<n;i++){
		for(long long j=0;j<=a[n]*n;j++) dp[i&1][j]=INF;
		for(long long j=0;j<=a[n]*n;j++) if(dp[(i&1)^1][j]!=INF){
			dp[i&1][j+b[i]]=min(dp[i&1][j+b[i]],dp[(i&1)^1][j]+b[i]*b[i]);
			dp[i&1][j+a[i]*i]=min(dp[i&1][j+a[i]*i],dp[(i&1)^1][j]+j*2*a[i]+a[i]*a[i]*i);
		}
	}
	for(long long i=0;i<=a[n]*(n-1);i++) if(dp[(n&1)^1][i]!=INF) ans=min(ans,n*dp[(n&1)^1][i]-i*i);
	cout<<ans;
}