霍格華茲的魔法表演
發布時間: Jan. 5, 2022, 2:52 p.m. 最後更新時間: Sept. 14, 2023, 10:32 p.m. 時間限制: 1000ms 記憶體限制: 256M
霍格華茲是所著名的魔法學校，最近他們打算讓部分的學生展示他們的魔法，每個學生都有一個數值代表他們的魔力值，但霍格華茲的學生眾多，每個人的魔力值也大不相同，教授想將學生表演的順序做調整，使得所有前 $i$ 位學生的最大魔力差距的和能變得最小，讓整個表演更加和諧。
假設有 $n$ 個學生要進行表演，定義第 $i$ 個要表演的學生為 $a_i$ 且其魔力值為 $s_i$ 。對於前 $i$ 位學生的表演，定義最大與最小魔力值差距為 $d_i$ ，即 $d_i = max(a_1,a_2,a_3,...,a_i) - min(a_1,a_2,a_3,...,a_i)$ ，請輸出整個表演順序經調整後，所有魔力差距和即 $d_1+d_2+d_3+...+d_n$ 的最小值。
第一行有一個整數 $n$ ，代表要表演的學生人數，$1 \leq n \leq 2000$。
第二行有 $n$ 個整數 $s_1,s_2,...,s_n$ 分別代表學生 $a_1,a_2,...,a_n$ 的魔力值, $1 \leq s_i \leq 10^9$
請輸出一個整數，代表調整表演順序後，所有魔力差距和(即 $d_1+d_2+d_3+...+d_n$ )的最小值。
複製範例
3 3 1 2
3
複製範例
1 5
0
複製範例
6 1 6 3 3 6 3
11
複製範例
6 104 943872923 6589 889921234 1000000000 69
2833800505
