题意

给定一个长度为\(n\)的数组\(a\),\(d[i]\)表示前\(i\)个数的最大值和最小值的差值，你可以随意选择数组顺序，求最小的\(d\)数组之和。

解法

想一下长度为\(n\)的最后一个\(d[i]\)，它的值一定是当前数组的最大值减去最小值，那么我们之能通过减少前\(n-1\)个位置的答案来维护最小值。也就是说，对于一个长度为\(n\)的区间来说，当前区间的答案可以由小区间的答案推导而来，即区间DP。
设定\(dp[i][j]\)表示区间\(i-j\)的最小值，那么转移方程：\(dp[i][i + len] = \min(dp[i][i + len - 1],dp[i + 1][i + len]) + a[i + len] - a[i]\)

思考

看了lcy的一节区间DP和yxc的一节区间DP课，我自以为是的觉得区间DP掌握了，不就是枚举长度，枚举起点，枚举中间点三层循环嘛然后遇到题就被爆锤了，其实无论哪个算法或者想法来说，你紧紧是学会了那个例题的思考方式，而最关键的是举一反三的融会贯通的能力。
看到题目的时候发现有贪心的标签，就去想了想，想了中错误的贪心，发现怎么都贪不过去，但是能很显然的明白最后一步的值一定是最大值减去最小值，那么把当前状态转移一下，就是一个基础的区间DP。

int n;
void solve() {
    cin >> n;
    vector<int>  a(n + 1);
    for(int i = 1;i <= n;++i) cin >> a[i];
    sort(a.begin() + 1,a.end());
    vector<vector<ll> > dp(n + 1,vector<ll>(n + 2,0));
    for(int len = 1;len < n;++len) {
        for(int i = 1;i + len <= n;++i){
            dp[i][i + len] = min(dp[i][i + len - 1],dp[i + 1][i + len]) + a[i + len] - a[i];
        }
    }
    cout << dp[1][n] << endl;
}

CF 1509-The Sports Festival

原文：https://www.cnblogs.com/Wise-XiaoWei4/p/14825380.html