分级

描述: 给一个序列A，要求求出另一个序列B， 最小化 S=∑Ni=1|Ai−Bi|。

A’序列就是A序列排序后的结果

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6, INF = 0x3f3f3f3f;
ll n;
ll a[maxn], b[maxn];
ll f[2010][2010]; // 以前i个结尾最后一个等于A'[j]的最小值。

ll dp()
{
    for(int i = 1; i <= n; i ++) b[i]=  a[i];
    sort(b+1, b+1+n);  // 得到A'序列

    // f[i][j]  before i numbers  and b[i] = a'[i]
    // f[i][j] = min(i-1个结尾小于等于j最小的, f[i-1][j] + abs(a[i] - b[j]))
    for(int i = 1; i <= n; i ++)
    {
        ll pre = INF;  // pre表示在i-1个元素的时候，最后一个结尾是小于等于j的最小值，并且用它来更新
        for(int j = 1; j <= n; j ++)
        {
            pre = min(pre, f[i-1][j]);
            f[i][j] = pre + abs(a[i] - b[j]);
        }
    }

    ll res = INF;

    for(int i = 1; i <= n; i ++)
    {
        res = min(res, f[n][i]);
    }
    return res;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    ll res = dp();
    reverse(a+1, a+1+n);
    res =min(res, dp()); // 反转一下求递减的

    cout << res << endl;
    return 0;
}