区间DP

题意

给n个数。定义。
你可以随意排列这n个数，求的可能的最小值。

solution

比较有意思的区间DP：表示从到的最小。
排序后，每次向左或向右拓展一位，都会更新最小值/最大值

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[2005], n;
ll dp[2005][2005];
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + 1 + n);
    for (int len = 1; len < n; ++len) {
        for (int L = n - len, R = n; L; --L, --R) {
            dp[L][R] = min(dp[L + 1][R], dp[L][R - 1]) + a[R] - a[L];
        }
    }
    cout << dp[1][n] << '\n';
    return 0;
}