首先对于一段区间,中位数肯定是最优。
之后就是一个极水的$DP$
$f_{k+1,r}=\min\{f_{k+1,r},f_{k-1,l-1}+val_{l,r}\}$
求$val_{l,r}$时,这哪里是堆优化,明明就是一棵主席树嘛。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=2005,M=2e4+5;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}/*
struct node{int d,son[2],f,n,c,s;}t[N];int len,root;
inline void add(int d,int f){t[++len]=(node){d,{0,0},f,1,1,d};t[f].son[t[f].d<d]=len;}
inline void update(int p){t[p].c=t[p].n+t[t[p].son[0]].c+t[t[p].son[1]].c;t[p].s=t[t[p].son[0]].s+t[t[p].son[1]].s+t[p].d*t[p].n;}
void rotate(int p,int w)
{
    int f=t[p].f,gf=t[f].f;
    int r=t[p].son[w],R=f;t[R].son[w^1]=r;if(r)t[r].f=R;
    r=p;R=gf;t[R].son[t[R].son[1]==f]=r;t[r].f=R;
    r=f;R=p;t[R].son[w]=r;t[r].f=R;update(f),update(p);
}
void splay(int p,int rt)
{
    while(t[p].f!=rt)
    {
        int f=t[p].f,gf=t[f].f;
        if(gf==rt)rotate(p,t[f].son[0]==p);
        else 
        {
            if(t[f].son[0]==p&&t[gf].son[0]==f)rotate(f,1),rotate(p,1);
            else if(t[f].son[1]==p&&t[gf].son[0]==f)rotate(p,0),rotate(p,1);
            else if(t[f].son[0]==p&&t[gf].son[1]==f)rotate(p,1),rotate(p,0);
            else rotate(f,0),rotate(p,0);
        }
    }
    if(!rt)root=p;
}
int get_id(int d)
{
    int p=root;
    while(t[p].d!=d)
    {
        if(t[p].d<d)
        {
            if(!t[p].son[1])break;
            p=t[p].son[1];
        }
        else
        {
            if(!t[p].son[0])break;
            p=t[p].son[0];
        }
    }
    return p;
}
void ins(int d)
{
    if(!root){add(d,0);root=len;return ;}
    int p=get_id(d);
    if(t[p].d==d)++t[p].n,update(p),splay(p,0);
    else add(d,p),update(p),splay(len,0);
}
int kth(int k)
{
    int p=root;
    while(233)
    {
        int lc=t[p].son[0],rc=t[p].son[1];
        if(t[lc].c>=k)p=lc;
        else if(t[lc].c+t[p].n<k)k-=t[lc].c+t[p].n,p=rc;
        else break;
    }
    splay(p,0);
    return t[p].d*t[t[p].son[0]].c-t[t[p].son[0]].s+t[t[p].son[1]].s-t[t[p].son[1]].c*t[p].d;
}*/
struct HJTseg{int sum,l,r,s;}t[M<<4];int cnt,root[N];
void update(int l,int r,int &x,int y,int pos)
{
    t[x=++cnt]=t[y];++t[x].sum;t[x].s+=pos;
    if(l==r)return ;
    int mid=l+r>>1;
    if(pos<=mid)update(l,mid,t[x].l,t[y].l,pos);
    else update(mid+1,r,t[x].r,t[y].r,pos);
}
int s1,s2,c1,c2;
int query(int l,int r,int x,int y,int k)
{
    if(l==r){c1+=t[x].sum-t[y].sum;s1+=t[x].s-t[y].s;return l;}
    int mid=l+r>>1,sum=t[t[x].l].sum-t[t[y].l].sum;
    if(k<=sum){c2+=t[t[x].r].sum-t[t[y].r].sum;s2+=t[t[x].r].s-t[t[y].r].s;return query(l,mid,t[x].l,t[y].l,k);}
    else {c1+=t[t[x].l].sum-t[t[y].l].sum;s1+=t[t[x].l].s-t[t[y].l].s;return query(mid+1,r,t[x].r,t[y].r,k-sum);}
}
int f[N][N],a[N],ans[26][N];
int main()
{
    //freopen("d1.in","r",stdin);
    int n,m,T=0;
    while(qr(n),qr(m),n&&m)
    {
        ++T;        
        int mx=0;cnt=0;
        for(int i=1;i<=n;i++)qr(a[i]),a[i]+=10000,mx=max(a[i],mx);
        if(T==7)
            T++,T--;
        for(int i=1;i<=n;i++)update(1,mx,root[i],root[i-1],a[i]);
        for(int l=1;l<=n;l++)
        {
            for(int r=l;r<=n;r++)
            {
                s1=s2=c1=c2=0;
                int pos=query(1,mx,root[r],root[l-1],(l+r+1>>1)-l+1);
                f[l][r]=pos*c1-s1+s2-pos*c2;
            }
        }
        memset(ans,0x3f,sizeof(ans));
        for(int i=1;i<=n;i++)ans[1][i]=f[1][i];
        for(int i=2;i<=m;i++)
            for(int l=i-1;l<n;l++)
                for(int r=l+1;r<=n;r++)
                {
                    ans[i][r]=min(ans[i][r],ans[i-1][l]+f[l+1][r]); 
                }
        qw(ans[m][n]);puts("");
    }
    return 0;
}