题意分析

题目要求将一个整数序列转换为$k$-单调序列所需的最小操作次数。$k$-单调序列可以被分解为$k$个严格单调的连续子序列。每次操作可以将任意元素增加或减少$1$。

解题思路

1. 预处理成本：计算将任意子序列转换为严格递增或递减序列的最小操作次数。
2. 左偏树优化：使用左偏树高效计算中位数，从而确定最优调整值。
3. 动态规划：利用预处理好的成本，通过动态规划找到将整个序列划分为$k$个子序列的最小总成本。

实现步骤

1. 预处理阶段：
   • 对原序列进行变换，计算两种可能的单调序列（递增和递减）的成本。
   • 使用左偏树维护中位数，计算每个子序列的调整成本。
2. 动态规划阶段：
   • 初始化$dp$数组，$dp[i][j]$表示前$i$个元素划分为$j$个子序列的最小成本。
   • 通过状态转移方程更新$dp$值：$dp[i][j] = \min(dp[k-1][j-1] + cost[k][i])$。
3. 结果输出：取$dp[n][k]$的最小值作为答案。

C++实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define Maxn 1100

struct LeftistTree{
    int l,r,dis,v,cnt;
    void init(int val){
        l=r=dis=0;v=val;cnt=1;
    }
}lt[Maxn];
int tt;

int merge(int a,int b){
    if (a==0) return b;
    if (b==0) return a;
    if (lt[a].v<lt[b].v) swap(a,b);
    lt[a].r=merge(lt[a].r,b);
    if (lt[lt[a].l].dis<lt[lt[a].r].dis) swap(lt[a].l,lt[a].r);
    if (lt[a].r==0) {lt[a].dis=0;}
    else {lt[a].dis=lt[lt[a].r].dis+1;}
    return a;
}

int gettop(int a){
    return lt[a].v;
}

int pop(int a){
    int l=lt[a].l,r=lt[a].r;
    lt[a].init(0);
    return merge(l,r);
}

int insert(int root,int nval){
    lt[++tt].init(nval);
    return merge(root,tt);
}

void initLT(){
    int i;
    tt=0;
    for(i=1;i<=Maxn-10;++i){
        lt[i].init(0);
    }
}

int costb[Maxn][Maxn],costc[Maxn][Maxn];
int b[Maxn],c[Maxn];
int val[Maxn];
int sta[Maxn],pos[Maxn],smallsum[Maxn],smallcnt[Maxn],bigsum[Maxn],bigcnt[Maxn];
int n,t;

void prework(int v[],int cost[Maxn][Maxn]){
    int i,j,tv,top,tpos,tcnt;
    for(i=1;i<=n;++i){
        top=0;
        initLT();
        cost[i][i-1]=0;
        pos[0]=i-1;
        smallsum[0]=0;
        smallcnt[0]=0;
        bigsum[0]=0;
        bigcnt[0]=0;
        for(j=i;j<=n;++j){
            lt[++tt].init(v[j]);
            sta[++top]=tt;
            pos[top]=j;
            smallsum[top]=v[j];
            smallcnt[top]=1;
            bigsum[top]=0;
            bigcnt[top]=0;
            while(top>1){
                if (lt[sta[top]].v<lt[sta[top-1]].v){
                    sta[top]=merge(sta[top],sta[top-1]);
                    smallsum[top-1]+=smallsum[top];
                    smallcnt[top-1]+=smallcnt[top];
                    bigsum[top-1]+=bigsum[top];
                    bigcnt[top-1]+=bigcnt[top];
                    top--;
                    tcnt=(j+2-pos[top])/2;
                    while(smallcnt[top]>tcnt){
                        tv=gettop(sta[top]);
                        sta[top]=pop(sta[top]);
                        smallcnt[top]-=1;smallsum[top]-=tv;
                        bigcnt[top]+=1;bigsum[top]+=tv;
                    }
                }
                else break;
            }
            tpos=pos[top]-1;
            tv=gettop(sta[top]);
            cost[i][j]=cost[i][tpos]+smallcnt[top]*tv-smallsum[top]+bigsum[top]-tv*bigcnt[top];
        }
    }
}

int f[Maxn][Maxn];

int main(){
    int i,j,k;
    int inf;
    while(scanf("%d%d",&n,&t)&&(n||t)){
        for(i=1;i<=n;++i){
            scanf("%d",&val[i]);
            b[i]=val[i]-i;
            c[n+1-i]=val[i]-(n+1-i);
        }

        prework(b,costb);
        prework(c,costc);
        for(i=1;i<=n;++i){
            for(j=i;j<=n;++j){
                costb[i][j]=min(costb[i][j],costc[n+1-j][n+1-i]);
            }
        }
        inf=500000000;
        for(i=0;i<=n;++i)
            for(j=0;j<=n;++j) f[i][j]=inf;

        f[0][0]=0;
        for(i=1;i<=n;++i){
            for(j=1;j<=t;++j){
                for(k=1;k<=i;++k){
                    if (f[k-1][j-1]+costb[k][i]<f[i][j]) f[i][j]=f[k-1][j-1]+costb[k][i];
                }
            }
        }
        int ans=inf;
        for(i=1;i<=t;++i)if (ans>f[n][i]) ans=f[n][i];
        printf("%d\n",ans);
    }
    return 0;
}

代码说明

1. 左偏树实现：

   • 用于高效维护中位数，支持合并、插入和删除操作。
   • merge函数实现树的合并，gettop获取堆顶元素，pop删除堆顶元素。

2. 预处理函数prework：

   • 计算将子序列转换为单调序列的最小操作成本。
   • 使用左偏树动态维护中位数，计算调整成本。

3. 动态规划求解：

   • f[i][j]表示前$i$个元素划分为$j$个子序列的最小成本。
   • 通过三重循环更新$dp$值，考虑所有可能的子序列划分。

4. 复杂度分析：

   • 预处理阶段复杂度为$O(n^2 \log n)$。
   • 动态规划阶段复杂度为$O(n^2 k)$。
   • 总体复杂度在题目限制范围内可行。