CF1197C Array Splitting

给定一个有序数组 $a_1, a_2, \dots, a_n$（对于每个 $i > 1$，都有 $a_i \ge a_{i-1}$），以及一个整数 $k$。 你需要将该数组划分为 $k$ 个非空连续子数组。数组中的每个元素必须且只能属于一个子数组。 设第 $i$ 个子数组的最大值为 $max(i)$，最小值为 $min(i)$。划分的代价定义为 $\sum\limits_{i=1}^{k} (max(i) - min(i))$。例如，若 $a = [2, 4, 5, 5, 8, 11, 19]$，将其划分为 $3$ 个子数组：$[2, 4], [5, 5], [8, 11, 19]$，则划分代价为 $(4 - 2) + (5 - 5) + (19 - 8) = 13$。 请计算将数组 $a$ 划分为 $k$ 个非空连续子数组所能得到的最小代价。

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 3 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$，$a_i \ge a_{i-1}$）。

输出将数组 $a$ 划分为 $k$ 个非空连续子数组所能得到的最小代价。

在第一个测试样例中，可以将数组 $a$ 划分为：$[4, 8, 15, 16], [23], [42]$。 由 ChatGPT 4.1 翻译