题目链接:https://www.luogu.org/problemnew/show/P3080

题解:不妨定义dp[i][j][0/1]dp[i][j][0/1]表示[i,j][i, j]区间已经完成并且此时站在左边或者右边
那么直接一个区间dp的转移即可,具体转移代码参见代码

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1005 + 5;
int a[MAXN];
int f[MAXN][MAXN][2];
int n;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    mem(f, INF);
    for(int i = 1; i <= n; i++) f[i][i][0] = f[i][i][1] = abs(a[i]) * n;
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i + k - 1 <= n; i++) {
            int j = i + k - 1;
            int num = n - j + i;
            f[i][j][0] = min(f[i+1][j][0] + (a[i+1]-a[i]) * num, f[i][j][0]);
            f[i][j][0] = min(f[i+1][j][1] + (a[j]-a[i]) * num, f[i][j][0]);
            f[i][j][1] = min(f[i][j-1][0] + (a[j]-a[i]) * num, f[i][j][1]);
            f[i][j][1] = min(f[i][j-1][1] + (a[j]-a[j-1]) * num, f[i][j][1]);
        }
    }
    cout << min(f[1][n][0], f[1][n][1]);
    return 0;
}