题目地址：https://www.acwing.com/problem/content/2723/

　　题意：将一段序列变成k段，每一段内部严格单调递减或严格单调递增，成这样的序列为k单调序列，为构造这样的k单调序列最小花费是多少

（花费是对应元素之差的绝对值）

　　分析：　　是数字序列的拓展，么一段内部都是严格单调序列可已转化成求非严格单调序列

　　　　　　　定义cost[i][j]为将区间i到j变成单调序列（非降或非增）的最小花费

　　　　　　　f[i][k]将长度为i的序列变成k单调序列的最小话费是多少

　　　　　　　cost[i][j] 可以用数字序列的方法用O（n^2logn）的时间复杂度求出来

　　　　　　　枚举区间的起点i然后求出从i开始的所有区间变成单调递增区间的最小花费

　　　　　　　然后在按相同的方式枚举求出所有以i为起点的区间变成单调递减区间的最小话费两者取min

　　　　　　    求单调递减序列和求原序列所有数加上负号后构造一个单调递增序列是相同的

　　　　　　   

　　　　　　细节快速求序列对定值的相差的绝对值之和的求法

　　　　　　维护左偏树的大小 tree_sz

　　　　　　左偏树的节点权值的总和 tree_sum

　　　　　　维护整个区间的大小 tot_sz

　　　　　　维护整个区间的权值之和  tot_sum

　　　　　　由于中位数就是左偏树最大值整理定义为mid

　　　　　　ans = mid * tree_sz - tree_sum + tot_sum - tree_sum - (tot_sz - tree_sz) * mid;

 

　　　　　　f的状态转移方程：

　　　　　　先从小打大枚举区间的长度然后枚举要将这段区间分成几个单调区间

　　　　　　再根据最后一段区间的长度将集合划分

　　　　　　f[i][k] = min(f[i][k],min{f[i-j][k-1] + cost[]i - j + 1[i]}

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

using namespace std;
const int N = 1010;
int l[N],r[N],dist[N],v[N];
int a[N];
struct Segment
{
    int root;
    int tree_sum;
    int tree_sz;
    int tot_sz;
    int tot_sum;
    int get()
    {
        int mid = v[root];
        // cout << mid << " "<< tree_sz << " "<< tree_sum << " "<< tot_sz << " "<< tot_sum << endl;
        return mid * tree_sz - tree_sum + tot_sum - tree_sum - (tot_sz - tree_sz) * mid;
    }
}stk[N];
int n,m;
int cost[N][N],f[N][12];

int merge(int x,int y)
{
    if(!x || !y) return x + y;
    if(v[y] > v[x]) swap(x,y);
    r[x] = merge(r[x],y);
    if(dist[r[x]] > dist[l[x]]) swap(l[x],r[x]);
    dist[x] = dist[r[x]] + 1;
    return x;
}

int pop(int x)
{
    return merge(l[x],r[x]);
}

void get_cost(int u)
{
    int res = 0;
    int tt = 0;
    for(int i = u;i <= n;i ++)
    {
        l[i] = r[i] = 0;
        dist[i] = 1;
        auto ver = Segment({i,v[i],1,1,v[i]});
        while(tt && v[ver.root] < v[stk[tt].root])
        {
            res -= stk[tt].get();
            // cout << stk[tt].get() << endl;
            ver.root = merge(stk[tt].root,ver.root);//记得要改变区间根节点
            ver.tree_sum += stk[tt].tree_sum;
            ver.tot_sum += stk[tt].tot_sum;
            bool flag = (ver.tot_sz % 2 && stk[tt].tot_sz % 2);
            ver.tree_sz += stk[tt].tree_sz;
            ver.tot_sz += stk[tt].tot_sz;
            if(flag)
            {
                ver.tree_sum -= v[ver.root];
                ver.tree_sz --;
                ver.root = pop(ver.root);
            }
            tt--;
        }
        // cout << ver.get() << " "<< v[ver.root] << endl;
        res += ver.get();
        stk[++tt] = ver;
        cost[u][i] = min(cost[u][i],res);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    memset(cost,0x3f,sizeof cost);
    for(int i = 1;i <= n;i ++) v[i] = a[i] - i;
    for(int i = 1;i <= n;i ++) get_cost(i);
    for(int i = 1;i <= n;i ++) v[i] = -a[i] - i;
    for(int i = 1;i <= n;i ++) get_cost(i);
    
    memset(f,0x3f,sizeof f);
    f[0][0] = 0;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            for(int k = 1;k <= i;k ++)
                f[i][j] = min(f[i][j],f[i - k][j - 1] + cost[i - k + 1][i]);
    
    printf("%d\n",f[n][m]);
    return 0;
}