给定一个长度为 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;
}