算法

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

首先，这道题让我们选出一个运动员的出场顺序，但是我们发现没办法贪心。

其次，通过观察可以发现如下性质：

假设我们现在已经选出了 $k$ 个人，不妨记为 $a_1, a_2, \dots a_k$，现在我们要选第 $k + 1$ 个人，我们分三种情况考虑：
- 假设我们选的这个人的速度比前 $k$ 个人的速度更快，即 $a_{k + 1} > \max\{a_1, a_2, \dots, a_k\}$，那么他对答案的贡献就是 $a_{k + 1} - \min\{a_1, a_2, \dots, a_k\}$。
- 这个人的速度很慢，即 $a_{k + 1} \min\{a_1, a_2, \dots, a_k\}$，那么他对答案的贡献就是 $\max\{a_1, a_2, \dots, a_k\} - a_{k + 1}$
- 这个人的速度一般，即 $\min\{a_1, a_2, \dots, a_k\} < a_{k + 1} < \max\{a_1, a_2, \dots, a_k\}$，那么他对答案的贡献就是 $\max\{a_1, a_2, \dots, a_k\} - \min\{a_1, a_2, \dots, a_k\} < a_{k + 1}$。

显然第三种方式对答案的贡献是最小的，也就是说，我们现在有一个包含 $k$ 个人的集合，我们选第 $k + 1$ 个人的正确做法是选速度一般的人，这个人对答案的贡献最小。更形式化地，$\min\{a_1, a_2, \dots, a_k\}a_{k + 1} \leqslant \max\{a_1, a_2, \dots, a_k\}$。如果这样的人已经选完了，我们就要选择一个速度更快或更慢的人，并且要和我们选的 $k$ 个人水平接近。按照我们之前的分析，也就是让 $a_{k + 1} - \min\{a_1, a_2, \dots, a_k\}$，或者是 $\max\{a_1, a_2, \dots, a_k\} - a_{k + 1}$ 最小，我们可以先给数组排序，然后再选择连续的子数组。注意到这是一个局部最优解，并不是全局最优解，原因在于前两种情况的决策上。假如这两个人（更快的与更慢的）对答案的贡献一样，这就不太好区分选择谁了。所以，这两种情况都要考虑进去，我们可以采取区间 $dp$。

为了能进行这样的选择方式，首先要给数组进行排序，使得 $a_1 < a_2 < \dots a_n$。
假设我们选的第一个人是 $a_k$，我们选的下一个是 $a_{k + 1}$ 或 $a_{k - 1}$（按之前给的策略来选）
假设我们现在已经选出了 $a_K, a_{k + 1}, \dots, a_s$，我们下一步要选的是 $a_{k - 1}$ 或 $a_{s + 1}$

最后，我们选出集合 $a_1, a_2, \dots, a_n$

这里我们发现，我们选择的策略都是一样的，唯一的区别就是第一个选谁，所以我们先枚举第一个选谁，然后按照之前的策略选择即可。

C++ 代码

#include <bits/stdc++.h>
#define rrep(i, n) for (int i = 1; i <= (n); ++i)

using std::cin;
using std::cout;
using std::min;
using ll = long long;

const int N = 2010;

int s[N];
ll f[N][N];

int main() {
    int n;
    cin >> n;
    rrep(i, n) cin >> s[i];

    std::sort(s + 1, s + n + 1);

    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            f[l][r] = min(f[l][r - 1] , f[l + 1][r]) + s[r] - s[l];
        }
    }

    cout << f[1][n] << '\n';

    return 0;
}