題意：對于給定的整型數組$a$，每次選擇其中一個元素$a_i$（不能重復選擇同一元素），每次計算已選擇的元素的極差（最大元素減最小元素的差），輸出最后極差和的最小可能值

思路：（賽后補題）采用二維動態規劃，最后一個極差一定是整個數組的極差（$a_{max}?a_{min}$），而前一個極差無非有兩種情況：

• 剔除最小的元素，即整個數組中最大減去最次小
• 剔除最大的元素，即整個數組中最次大減去最小

若不剔除兩邊的元素，而是中間的元素的話，極差則與最后一個極差一致，而最后一個極差一定是最大的極差，顯然不符合最小化的要求
$dp[i][j]$表示剔除$i$個最小元素和$j$個最大元素，$dp[0][0]$則表示最后一個極差，將數組升序排序后，由上面的討論可得到狀態轉移方程：

$dp[i][j]=min(dp[i?1][j],d[i][j?1])+(a_{n?1?j}?a_i)$

當$i+j=n?1$時即說明已完成，此時$n?1?j=i$極差的減數與被減數指向同一元素，即最初只選擇了一個元素時的情況
最后的答案等于，$dp$數組中滿足$i+j=n?1$的最小元素值，顯然有$n$個元素滿足條件，每個元素即代表了最初選擇數組中每個$a_i$所能得到的最小結果

#include<bits/stdc++.h>
#define debug1(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef unsigned long long ull;
const int N = 2010;
const int MOD = 10000;
using namespace std;
int a[N];
ll dp[N][N];
int main()
{int n;cin>>n;for(int i = 1; i <= n; i++) cin>>a[i];sort(a+1, a+n+1);dp[0][0] = a[n] - a[1];for(int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + (a[n-j] - a[1]);for(int i = 1; i < n; i++) dp[i][0] = dp[i-1][0] + (a[n] - a[1+i]);ll ex;for(int i = 1; i < n; i++){for(int j = 1; i + j < n; j++){ex = a[n-j] - a[1+i];dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + ex;}}ll ans = dp[0][n-1];for(int i = 0; i < n; i++){ans = min(ans, dp[i][n-1-i]);}cout<<ans<<"\n";return 0;
}