題意：給你一個序列，你可以對它重新排序，然后使每個i，max(a0,a1……ai)-min(a0,a1……ai)最小。問答案是多少

思路：? ?C. The Sports Festival（區間DP）-CSDN博客

區間dp，完全沒想到。

首先有兩個觀察點很簡單
1.一個已經選擇好的序列，添加進來的數，如果是最小，或者最大會更新狀態，否則不。
2.在添加的過程中，添加進來的數改變兩個最值的時候越延遲，次數越多越好。
1 3 2是比1 2 3 差的，因為1 3代替了1 2計算了一次。

在這個基礎上使用區間dp，一個區間更新的情況就是新的最大值進入，或者最小值進入
狀態轉移方程得dp[l][r]=min(dp[l][r-1],dp[l+1][r])+a[r]-a[l]（更新的情況一定是新區間的兩個最值相加，但是不知道更新的是小還是大）可以說用上了一點貪心，排序過后一些很差的答案都被排除掉了，以及這個答案的更新。

代碼：

#include <bits/stdc++.h>
#define int long long
#define IOS std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0)const int MOD=1e9+7;
const int N=1e7+10;void solve(){int n;std::cin >> n;std::vector<int> ve(n);std::vector<std::vector<int>> dp(n,std::vector<int>(n,0));for(int i=0;i<n;i++){std::cin >> ve[i];}sort(ve.begin(),ve.end());for(int l=2;l<=n;l++){for(int i=0;i+l-1<n;i++){dp[i][i+l-1]=std::min(dp[i][i+l-2],dp[i+1][i+l-1])+ve[i+l-1]-ve[i];}}std::cout << dp[0][n-1] << '\n';}signed main(){IOS;int t=1;// std::cin >> t;while(t--){solve();}
}