题目内容

在模型量化中，当数据分布极度不均匀时，全局统一缩放会造成大量精度损失。一种优化策略是将数据划分为若干连续区间（分段），每段内部使用独立的常数值（代表值）进行近似，从而在保证压缩率的同时最小化总体误差。

本题要求实现一种最优分段算法：给定已排序的数据序列，将其划分为至多 $K$ 个连续区间，每个区间的所有数据被替换为该区间内的某个代表值（该值不必是输入中的数，但为简化本题，代表值必须是区间中位数取整后的值）。目标是使得所有数与对应代表值的绝对误差之和最小。

输入描述

第 $1$ 行：$N\ K$（$1\leq N\leq5000$，$1\leq K\leq\min(50,N)$）

第 $2$ 行：$N$ 个已按非降序排列的整数

• 量化规则：

1. 将序列划分为至多 $K$ 个连续区间

2. 对每个区间 $[l,r]$，计算其中位数 $\mathrm{med}$（若长度为偶数，取下中位数，即第 $\left\lfloor(l+r)/2\right\rfloor$ 个数）

3. 区间误差代价

   $cost(l,r)=\sum_{i=l}^{r}|a_i-rep|$

• 目标：

在满足区间数量 $\leq K$ 的前提下，最小化总代价 $total=\sum cost(l_i,r_i)$

输出描述

一个整数，表示最小总代价

样例1

输入

3 1
1 2 3

输出

2

样例2

输入

5 2
1 2 10 11 12

输出

3

说明

• 不分段（$K=1$）：中位数是 $10$，代价 $|1-10|+|2-10|+|10-10|+|11-10|+|12-10|=9+8+0+1+2=20$

• 最优分段（$K=2$）：划分为 $[1,2]$ 和 $[3,5]$

  第一段中位数 $2$，代价 $|1-2|+|2-2|=1$

  第二段中位数 $11$，代价 $|10-11|+|11-11|+|12-11|=1+0+1=2$

• 总代价 $3$