C++14(g++5.4) 解法, 执行用时: 27ms, 内存消耗: 16364K, 提交时间: 2020-06-05 12:39:16

#include <bits/stdc++.h>
using namespace std;
const int MX = 1e3+7;
int dis[MX];
long long f[MX][MX][2];
int main()
{
    int n;
    cin>>n;
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &dis[i]);
    }
    n++;
    sort(dis+1, dis+n+1);
    memset(f, 127, sizeof f);
    int x = 0;
    for(int i = 1; i <= n; ++i)
        if(dis[i] == 0) x = i;
    f[x][x][0] = f[x][x][1] = 0;
    for(int len = 2; len <= n; ++len)
    for(int l = 1, r = len; r <= n; ++l, ++r)
    {
        f[l][r][0] = min(f[l+1][r][0]+(dis[l+1]-dis[l])*(n-len+1), f[l+1][r][1]+(dis[r]-dis[l])*(n-len+1));
        f[l][r][1] = min(f[l][r-1][0]+(dis[r]-dis[l])*(n-len+1), f[l][r-1][1]+(dis[r]-dis[r-1])*(n-len+1));
    }
    cout<<min(f[1][n][0],f[1][n][1]);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 11ms, 内存消耗: 8580K, 提交时间: 2020-05-31 17:10:36

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
int dp[N][N][2],p[N];
int main(){
	memset(dp,0x3f3f,sizeof(dp));
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&p[i]);
	}
	sort(p+1,p+n+1);
	for(int i=1;i<=n;++i){
		dp[i][i][0]=dp[i][i][1]=n*abs(p[i]);
	}
	for(int i=n;i;--i){
		for(int j=i+1;j<=n;++j){
			int L=n-(j-i);
			dp[i][j][0]=min(dp[i+1][j][0]+L*(p[i+1]-p[i]),dp[i+1][j][1]+L*(p[j]-p[i]));
			dp[i][j][1]=min(dp[i][j-1][1]+L*(p[j]-p[j-1]),dp[i][j-1][0]+L*(p[j]-p[i]));
		}
	}
	printf("%d",min(dp[1][n][0],dp[1][n][1]));
	system("pause");
	return 0;
}