思路分析

这道题最难的是性质，在满足 S 最小化的前提下，一定存在一种构造序列b的方案，是的b中的数值都在a中出现过

性质了解后，我们直接用吧，首先我们可以类似LIS问题那样把已经处理完的前缀序列长度 i 作为阶段，把和 i 匹配的那个数的下标j作为附加维度（因为b序列由性质可得都在a序列出现过，所以这里的j指的就是a序列的某一个数的下标），现在我们可以写出状态表示了

dp[i][j] : 代表所有给a[1] ~ a[i]分配好了值且最后一个b[i] = a’[j]的方案的集合；(这里的a’[j]指的是排序好的a的下表为j处的值)

下面的代码里有写状态计算，同时3维优化成2维的方法和LCIS那道题一样，注意的是下面的代码里的b是a数组排序之后的作为备选的一个数组，不是上面讲解中的b

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2010;

int a[N], b[N];
int dp[N][N];
int n;

//dp[i][j] = min(dp[i-1][k]) + abs(a[i] - b[j])     (1 <= k <= j) (1 <= j <= n) 
//已经处理的前缀序列长度划分阶段 1 <= i <= n
int work1(){
    for(int i = 1;i <= n;++i) b[i] = a[i];
    sort(b+1, b+1+n);
    for(int i = 1;i <= n;++i){
        int minv = INT_MAX;//dp[i-1][k] 的最小值 (1 <= k <= j)
        for(int j = 1;j <= n;++j){
            minv = min(minv, dp[i-1][j]);
            dp[i][j] = minv + abs(a[i] - b[j]);
        }
    }
    int res = INT_MAX;
    for(int i = 1;i <= n;++i) res = min(dp[n][i], res);
    return res;
}

int work2(){
    for(int i = 1;i <= n;++i) b[i] = a[i];
    sort(b+1, b+1+n, less<int>());
    for(int i = 1;i <= n;++i){
        int minv = INT_MAX;//dp[i-1][k] 的最小值 (1 <= k <= j)
        for(int j = 1;j <= n;++j){
            minv = min(minv, dp[i-1][j]);
            dp[i][j] = minv + abs(a[i] - b[j]);
        }
    }
    int res = INT_MAX;
    for(int i = 1;i <= n;++i) res = min(dp[n][i], res);
    return res;
}

int main(){
    cin >> n;
    for(int i = 1;i <= n;++i) cin >> a[i];
    //b 是递增的
    int ans = work1();
    //b 是递减的
    ans = min(ans, work2());
    cout << ans << endl;
    return 0;
}