估测断层

"47个节点亮着。"你说，"但它们的值不一样——有的高，有的低。我要估测整个区域的平均水平。"

"咋测？"

"分段。"你说，"把连续的节点切成段，每段用一个代表值——中位数。"

"中位数？"

"对。"你说，"一段数的中位数，能让这段的偏差之和最小。"

"偏差？"

"每个节点和中位数的差的绝对值。"你说，"中位数 minimises 这个和。"

"为啥不取平均？"

"平均受极端值影响。"你说，"中位数更稳。"

"那切几段？"

"看情况。"你说，"切得太细——每段节点少，估测不准。切得太粗——偏差大。要找最优分段数。"

"最优？"

"对。"你说，"$dp[i][j]$为前$i$个节点切成$j$段的最小偏差和。"

"转移？"

"$dp[i][j]=\min(dp[k][j-1]+cost(k+1,i))$。"你说，"$cost(k+1,i)$是这段的中位数偏差。"

"中位数咋快速求？"

"对顶堆。"你说，"维护一个大根堆和一个小根堆，动态求中位数。"

你开始写。先预处理所有区间的$cost$，然后DP。

"第一段。"你说，"节点1到5：10,20,30,40,50。中位数30。偏差=20+10+0+10+20=60。"

"第二段。"你说，"节点6到10：15,25,35,45,55。中位数35。偏差=20+10+0+10+20=60。"

"总偏差120。"

"如果合成一段。"你说，"中位数30（或35）。偏差更大——因为离散。"

"分段好。"

"对。"

CC把节点值刻在金属手臂上——歪歪扭扭的数字，像某种原始人的记账。

"刻这干啥？"

"怕忘。"她说，"你算你的，我记我的。"

"你不会忘。"

"我会。"她说，"所以我刻下来。"

Echo看着那些数字——10,20,30,40,50——像某种阶梯，通向某个高处。

"以前有人教我数过。"她说，"教我的人……我不记得了。"

"没关系。"你说，"我记得。"

题目描述

给定一个长度为$n$的序列，要分成$k$段。每段用一个值估计，最小化$\sum |A_i-\hat{A}_i|$。每段最优估计值=中位数。求最小总偏差。

输入格式

$n,k$。然后$n$个整数。

输出格式

最小总偏差。

输入样例

3
1 2 3

输出样例

3

提示

• $dp[i][j]$为前$i$个数分$j$段的最小偏差。
• 预处理$cost[l][r]$为区间$[l,r]$的中位数偏差。
• 用对顶堆动态维护中位数。
• $dp[i][j]=\min(dp[k][j-1]+cost[k+1][i])$。