乍一看似乎很难下手.
但是有一个显然的结论:当$k$为$[l,r]$中的中位数时,$\sum_{i=l}^r |a[i]-k|$最小.
总共有$n^2$个区间,我们用对顶堆预处理出这些区间的代价$cost[l][r]$,这部分的时间复杂度是$O(n^2logn)$

接下来考虑dp.f[i][j]表示到j,划分了i段的最小代价
$$f[i][j]=min_{p=0}^{j-1}f[i-1][p]+cost[p+1][j]$$
这部分的时间复杂度$O(n^2k)$

时限有32s,但是我还是被卡常了是什么操作…最后吸氧过的.

/**********/省略快读
#define MAXN 2011
#define MAXK 27
ll f[MAXK][MAXN],a[MAXN],cost[MAXN][MAXN],suml=0,sumr=0;//前面三个如上所述,suml表示左边大根堆中元素的和,sumr表示右边小根堆中元素的和
std::priority_queue<ll>q1;
std::priority_queue<ll,std::vector<ll>,std::greater<ll> >q2;//对顶堆
void clear()//清空对顶堆
{
    std::priority_queue<ll>tmp1;
    std::priority_queue<ll,std::vector<ll>,std::greater<ll> >tmp2;
    q1.swap(tmp1),q2.swap(tmp2);
    suml=sumr=0;
}
void push(ll val)//插入元素val
{
    if(q1.empty())q1.push(val),suml+=val;//插入大根堆还是小根堆
    else if(val>q1.top())q2.push(val),sumr+=val;
    else q1.push(val),suml+=val;
    while(q1.size()>q2.size()+1)//调整两个堆中的元素数量直至q2.size()<=q1.size()<=q2.size()+1
    {
        sumr+=q1.top();
        q2.push(q1.top());
        suml-=q1.top();
        q1.pop();
    }
    while(q1.size()<q2.size())
    {
        suml+=q2.top();
        q1.push(q2.top());
        sumr-=q2.top();
        q2.pop();
    }
}
int main()
{
    while(1)
    {
        ll n=read(),k=read();
        if(!n&&!k)break;
        for(ll i=1;i<=n;++i)a[i]=read();
        for(ll i=1;i<=n;++i)//预处理cost
        {
            clear();
            for(ll j=i;j<=n;++j)
            {
                push(a[j]);
                ll val=q1.top();
                cost[i][j]=val*q1.size()-suml;
                if(!q2.empty())cost[i][j]+=sumr-val*q2.size();
            }
        }
        memset(f,0x3f,sizeof f);
        f[0][0]=0;
        for(ll i=1;i<=k;++i)//dp
            for(ll j=1;j<=n;++j)
                for(ll pre=0;pre<j;++pre)
                    umin(f[i][j],f[i-1][pre]+cost[pre+1][j]);
        printf("%lld\n",f[k][n]);
    }
    return 0;
}