← 返回题目列表

Codeforces · 513/E2

E2. 子数组剪切

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

给定一个长度为 n 和数字 k 的数组。让我们从初始数组中选择 k 个不重叠的非空子数组。令 si 为从左到右顺序的第 i 个子数组的和。计算以下表达式的最大值:

|s1 - s2| + |s2 - s3| + ... + |sk - 1 - sk|

这里的子数组是数组的连续部分。

输入

输入的第一行包含两个整数 n 和 k。第二行包含 n 个整数——数组的元素。元素的绝对值不超过104。

该问题由两个子问题组成。子问题对输入有不同的约束。正确提交子问题将获得一些分数。子问题的描述如下。

- 在子问题 E1(9 点)中,约束 2 ≤ n ≤ 400、2 ≤ k ≤ min(n, 50) 将成立。
- 在子问题 E2(12 点)中,约束 2 ≤ n ≤ 30000、2 ≤ k ≤ min(n, 200) 将成立。

输出

输出一个整数——最大可能值。

示例

输入 #1

5 3
5 2 4 3 1

输出 #1

12

输入 #2

4 2
7 4 3 7

输出 #2

8

注意

考虑第一个样本测试。如果第一个子数组仅包含第一个元素,第二个子数组跨越接下来的三个元素,最后一个子数组仅包含最后一个元素,则获得最佳解决方案。这些子数组的和分别为 5、9 和 1。

考虑第二个样本测试。在最优解中,第一个子数组由前两个元素组成,第二个子数组仅由第三个元素组成。请注意,最后一个元素不属于此解决方案中的任何子数组。