daimayuan 668 体育节

题目描述

http://oj.daimayuan.top/course/10/problem/668

简要题意：给定一个长度为 $n$ 的序列 $a_i$，令 $d_i=max(a_1, a_2, \cdots, a_i)-min(a_1, a_2, \cdots, a_i)$，现在要求重新排列 $a$，使得 $\sum_{i=1}^nd_i$ 最小

$n\le 2000$

Solution

我们考虑向一个序列中添加一个最值，那么最值一定要放在序列的最后面，我们考虑用区间 $dp$ 来排序

这里我们容易想到将 $a_i$ 排序，令 $f_{i,j}$ 为区间 $[i,j]$ 重拍后的最小代价，容易得到 $f_{i,j}=\min(f_{i+1,j},f_{i,j-1})+a_i-a_j$

时间复杂度 $O(n^2)$

#include <iostream>
#include <algorithm>
#define maxn 2010
#define ll long long
using namespace std;

int n, a[maxn];

ll f[maxn][maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1); 
    for (int len = 2; len <= n; ++len)
        for (int i = 1, j = len; j <= n; ++i, ++j)
            f[i][j] = min(f[i + 1][j], f[i][j - 1]) + a[j] - a[i];
    cout << f[1][n] << "\n";
    return 0;
}