【补题】Codeforces Round 715 (Div. 2) C. The Sports Festival

题意：给你一个序列，你可以对它重新排序，然后使每个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();}
}