估算

给定一个长度为 N 的整数数组 A，你需要创建另一个长度为 N 的整数数组 B，数组 B 被分为 K 个连续的部分，并且如果 i 和 j 在同一个部分，则 B[i]=B[j]。

如果要求数组 B 能够满足 Σ|A[i]−B[i]| 最小，那么最小值是多少，请你输出这个最小值。

输入格式
输入包含多组测试数据。

对于每组测试数据，第一行包含两个整数 N 和 K。

接下来 N 行每行包含一个整数，表示完整的数组 A。

当输入为一行 0 0 时，表示输入终止。

输出格式
对于每组数据，输出一个最小值。

每个结果占一行。

数据范围
1≤N≤2000,
1≤K≤25,K≤N
数组 A 中元素的绝对值不超过 10000。

输入样例：
7 2
6
5
4
3
2
1
7
0 0
输出样例：
9

/**********/省略快读
#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;
}