← 返回题目列表

Codeforces · 1197/C

C. 数组分割

中文机器翻译题面 查看原题

给定一个排序数组 $$$a_1, a_2, \dots, a_n$$$ (对于每个索引 $$$i > 1$$$ 条件 $$$a_i \ge a_{i-1}$$$ 成立)和一个整数 $$$k$$$。

要求您将此数组划分为 $$$k$$$ 个非空连续子数组。数组中的每个元素都应该包含在一个子数组中。

令 $$$max(i)$$$ 等于第 $$$i$$$ 个子数组中的最大值,$$$min(i)$$$ 等于第 $$$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$$$ 非空连续子数组可以获得的最小成本。

示例

输入 #1

6 3
4 8 15 16 23 42

输出 #1

12

输入 #2

4 4
1 3 3 7

输出 #2

0

输入 #3

8 1
1 1 2 3 5 8 13 21

输出 #3

20

注意

在第一个测试中,我们可以按以下方式划分数组 $$$a$$$:$$$[4, 8, 15, 16], [23], [42]$$$。