体育节

数据规模：$1 \le n \le 2000$，$1 \le s_i \le 10^9$。

思路

先排序。 每个阶段的不协调值只取决于该阶段出场选手的最大速度与最小速度，与选手的原始编号无关。把速度升序排序为 $s_1 \le s_2 \le \dots \le s_n$，题目只问出场顺序，所以排序不改变答案。

把答案拆到相邻空隙上。 对某阶段的出场集合 $S$，设其中最小、最大速度分别是排序后的 $s_a, s_b$，则

$s_b - s_a = \sum_{j=a}^{b-1} (s_{j+1} - s_j).$

也就是说，相邻的每一对 $(s_j, s_{j+1})$ 贡献的空隙 $w_j = s_{j+1} - s_j$，只要该阶段同时出场了「编号 $\le j$ 的选手」和「编号 $> j$ 的选手」就被计入一次。于是总代价为

$\sum_{j=1}^{n-1} w_j \cdot c_j,$

其中 $c_j$ 是「同时出场了空隙 $j$ 两侧选手」的阶段个数。这等于 $n - M_j + 1$，$M_j$ 是空隙 $j$ 两侧都被占满的那个阶段（即第 $\max(\min_{k\le j} t_k,\ \min_{k>j} t_k)$ 个阶段，$t_k$ 是排序后第 $k$ 位选手的出场时刻）。要让总代价小，就要让每个空隙「填满」得尽量晚。

最优顺序可以取成区间扩张。 设第一个出场的是排序后的第 $m$ 位（$t_m = 1$）。

• 对 $j < m$：空隙右侧已经含第 $m$ 位，所以 $M_j = 1$，$c_j = n$，即这些空隙无论后面怎么排都是满代价 $n w_j$。
• 对 $j \ge m$：空隙左侧含第 $m$ 位，$M_j = \min_{k>j} t_k$，只由右侧选手的出场时刻决定。

现在考虑「从第 $m$ 位出发，先一直向左扩到 $1$，再一直向右扩到 $n$」这种具体顺序：排在 $j$ 号空隙两侧都出现的阶段时，左侧只需扩到 $j$，右侧需要扩到 $j+1$，于是 $j<m$ 时空隙的代价是 $n-m+j$，$j \ge m$ 时是 $n-j$。和任意顺序比：

• 左半部分：$j \le m-1$，故 $n-m+j \le n-1 < n$，不会更差；
• 右半部分：$> j$ 的位置共有 $n-j$ 个，它们的出场时刻是 $n-j$ 个互不相同的正整数，其中最小值至多为 $n-(n-j)+1 = j+1$，即 $\min_{k>j} t_k \le j+1$，故 $n+1-\min_{k>j} t_k \ge n-j$，也不会更差。

所以任何出场顺序都能被这个「区间扩张」顺序替代而不变差。反过来，任何区间扩张顺序都对应一个合法出场顺序，因此最优解恰是「从排序后某个位置开始，每次把区间向左或向右扩大一格」这类顺序的最优值。

状态与转移。 由于扩张过程中已出场的集合始终是排序后的一个连续区间 $[l,r]$，设 $f(l,r)$ 表示前 $r-l+1$ 个阶段（即已出场集合依次扩张到 $[l,r]$）的代价最小值。上一阶段要么是 $[l+1,r]$，要么是 $[l,r-1]$，而当前阶段的代价是 $s_r - s_l$：

$f(l,r) = (s_r - s_l) + \min\bigl(f(l+1,r),\ f(l,r-1)\bigr), \qquad f(i,i) = 0 .$

答案为 $f(1,n)$。按区间长度从小到大递推即可，等号说明重叠的速度值不影响正确性（对应空隙 $w_j = 0$，本来就不产生代价）。

为什么用二维表就够。 转移只依赖长度少一的两个区间，所以按长度递增计算、用二维数组直接存是最省事的写法。$n \le 2000$ 时状态数 $4 \times 10^6$，每个状态只做两次查表和一次加法。答案上界约 $n \cdot 10^9 = 2 \times 10^{12}$，需要 64 位整数。

复杂度

状态数 $O(n^2)$，转移 $O(1)$，时间 $O(n^2)$；存储 $O(n^2)$。

仓颉实现

二维表压缩成一维数组，下标为 $l\cdot(n+1)+r$，初始全为 $0$，正好对应 $f(i,i)=0$。

import std.env.*
import std.convert.*
import std.sort.*

main() {
    let n = Int64.parse(getStdIn().readln().getOrThrow())
    let s = getStdIn().readln().getOrThrow().split(" ", removeEmpty: true).map({ p: String => Int64.parse(p) })
    sort(s)
    let w = n + 1
    let dp = Array<Int64>(w * w, { _ => 0 })
    for (len in 2..=n) {
        for (l in 0..=(n - len)) {
            let r = l + len - 1
            let a = dp[(l + 1) * w + r]
            let b = dp[l * w + (r - 1)]
            var m = a
            if (b < a) {
                m = b
            }
            dp[l * w + r] = (s[r] - s[l]) + m
        }
    }
    println(dp[n - 1])
}