题目描述

学生会正在为体育节的接力赛做准备。

该理事会由n名成员组成。 他们将在比赛中一个接一个的奔跑，成员i的速度为s[i]。 第i个阶段的差异d[i]是跑步的前i个成员中最大跑步速度和最小跑步速度之间的差。 形式上，如果ai表示参加比赛的第i个成员的速度，则d[i] = max（a[1]，a[2]，…，a[i]）-min（a[1]，a[2]，…，a[i]）。

您要最小化差异d1 + d2 +⋯+ dn的总和。 为此，您可以更改成员的运行顺序。 可以达到的最小可能总和是多少？

样例

3
3 1 2

3

1
5

0

刚好最近在整区间dp

(区间dp) $O(n^2)$

首先观察一下第一个样例 3 1 2的最优值为3
要得到最小差异和则最大值或最小值必须出现在最后一位,否则如果都在最后一位之前出现
会导致最后一位之前已经取到最大差异值,而且后面也全是最大差异值!!!
比如 1 3 2 就会使得d[ 2 ]=3-1已经达到2了 后面的d[ 3 ]=3-1=2也是2
先按从小到大排序,也会发现末尾之前的元素是从小到大填的
通过排列可以得到 2 3 1 或1 2 3 的排列是最优的,
于是用y氏dp分析法得到
状态表示 f[i][j]表示区间[i,j]的最大差异和 属性 min
状态转移 f[ i ][ j ]=a[ j ]-a[ i ]+min(f[ i+1 ][ j ],f[ i ][j-1 ]);
因为末尾是最大值和最小值的一个那填了它们中的一个产生的贡献是a[j]-a[i]
f[ i+1 ][ j ]表示区间[i,j]把最小值填到最后一位,f[ i ][ j-1 ]表示区间[i,j]把最大值填到最后一位,

参考文献 CF官方题解

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =2010;
ll f[N][N],a[N];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++)   scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=1e18;
    sort(a+1,a+1+n);

    for(int i=1;i<=n;i++)  f[i][i]=0;

    for(int len=1;len<=n;len++)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            f[l][r]=min(f[l][r],a[r]-a[l]+min(f[l][r-1],f[l+1][r]));//末尾放最小值
            //和末尾放最大值
        }
    }
    printf("%lld\n",f[1][n]);
    return 0;
}