#6384. 「是男人就过8题——Pony.ai」SignLocation

内存限制:256 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

路上有 n 个车站,分别位于 x_1 ... x_n ( x_1 < x_2 < ... < x_n ) 处。

你的任务是选 k 个放标志的地方 (标志的位置不局限于车站,也可以在其它地方) 。 令 c(i,j) 表示第 i 个站与第 i 个和第 j 个站之间离第 i 个站最近的标记的距离,如果两个站直接没有标记,则 c(i,j) = |x_i - x_j| ,则你需要合理选择标志的位置以最小化 \sum_{i \neq j} c(i,j) 的值。

输入格式

输入包含多组测试数据,每组以两个整数 n k 开始。
接下来的一行包含 n 个整数 x_1, \dots , x_n

输出格式

对于每个测试数据,输出一个整数,代表 \sum_{i \neq j} c(i,j) 的最小值。

样例

样例输入

4 0
1 2 3 4
4 1
1 2 3 4

样例输出

20
11

数据范围与提示

对于 100\% 的数据, 0 \leq k \leq 200, 2 \leq n \leq 10000 , 0 \leq x_1 < x_2 < \ldots < x_n \leq 10^7

特别鸣谢楼天城和吉如一提供试题,数据。