分级

结论: 一定存在一组最优解 使得每个 b[i] 都是 a[i] 中的某个值
状态表示: 1. 集合 f[i][j] 表示处理到 b 的前 i 个， 并且当前选的是 a 里面的第 j 个的集合
          2. 属性 最小值
状态转移: f[i][j] = f[i - 1][k] + abs(a[i] - b[j]); { k = (0, j] }

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define INF 0x3f3f3f3f

using namespace std;

const int N = 2010;

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

int dp(){
    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 = INF;
        for(int j = 1;j <= n;j ++ ){
            minv = min(minv, f[i - 1][j]);
            f[i][j] = minv + abs(b[j] - a[i]);
        }
    }

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

    return res;
}

int main(){
    scanf("%d", &n);
    for(int i = 1;i <= n;i ++ ) scanf("%d", &a[i]);

    int res = dp();
    reverse(a + 1, a + 1 + n);
    res = min(res, dp());

    printf("%d\n", res);

    return 0;
}

估算

感觉这两个题很像

结论: 选择[l, r]中位数 可以最优化
状态表示: 1. 集合 f[i][j] 表示 b 选择到第 i 个并且已经选了 j 段的集合
          2. 属性 最小值
状态转移: f[i][j] = f[k][j - 1] + w[k + 1][j]; k = [j - 1, i - 1]

中位数(m) 可以用 对顶堆 来求或者 手写平衡树
cnt1(cnt2) 表示 所有 <= m(> m)数的个数
sz1(sz2) 表示 所有 <= m(> m)数的和
那么 w[l][r] = cnt1 * m - sz1 + sz2 - cnt2 * m

#pragma GCC optimize(2)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 2010, K = 26;

int n, k;
int a[N];
int w[N][N], s1, s2;
int dp[N][K];
priority_queue<int> p; // 大跟堆
priority_queue<int, vector<int>, greater<int>> q; // 小跟堆

void mem(){ 
    while(p.size()) p.pop();
    while(q.size()) q.pop();
    s1 = s2 = 0;
}
void add(int x) {
    if(p.empty() || x <= p.top()) p.push(x), s1 += x;
    else q.push(x), s2 += x;
    if(p.size() > q.size() + 1) {
        s2 += p.top(), s1 -= p.top();
        q.push(p.top()), p.pop();
    }else if(q.size() > p.size()){
        s2 -= q.top(); s1 += q.top();
        p.push(q.top()); q.pop();
    }
}
int query(){
    int sum = 0;
    int mid = p.top();
    if(p.size()) sum += mid * p.size() - s1;
    if(q.size()) sum += s2 - mid * q.size();
    return sum;
}

int main(){

    while(scanf("%d%d", &n, &k), n || k){
        memset(dp, 0x3f, sizeof dp);
        for(int i = 1;i <= n;i ++ ) scanf("%d", &a[i]);
        for(int i = 1;i <= n;i ++ ){
            mem();
            for(int j = i;j <= n;j ++ ){
                add(a[j]);
                w[i][j] = query();
            }
        }

        dp[0][0] = 0;
        for(int i = 1;i <= n;i ++ )
            for(int j = 1;j <= k;j ++ ){
                for(int k = j - 1;k < i;k ++ ){
                    dp[i][j] = min(dp[i][j], dp[k][j - 1] + w[k + 1][i]);
                }
            }
        printf("%d\n", dp[n][k]);
    }

    return 0;
}