CF513E2 Subarray Cuts

给定一个长度为 $n$ 的数组和一个数字 $k$。我们需要从初始数组中选择 $k$ 个不重叠且非空的子数组。设 $s_i$ 表示从左到右第 $i$ 个子数组的和。请计算下式的最大值： $$ |s_1 - s_2| + |s_2 - s_3| + \ldots + |s_{k-1} - s_k| $$ 这里的子数组指的是数组的连续一段。

输入的第一行包含两个整数 $n$ 和 $k$。第二行包含 $n$ 个整数，表示数组的元素。数组元素的绝对值不超过 $10^4$。 本题包含两个子任务，不同子任务对输入有不同的限制。你提交子任务的正确解答将获得相应分数。子任务描述如下： - 子任务 E1（9 分）：$2 \leq n \leq 400$，$2 \leq k \leq \min(n, 50)$。 - 子任务 E2（12 分）：$2 \leq n \leq 30000$，$2 \leq k \leq \min(n, 200)$。

输出一个整数，表示可能取得的最大值。

考虑第一个样例测试。最优解是第一个子数组只包含第一个元素，第二个子数组包含接下来的三个元素，最后一个子数组只包含最后一个元素。这些子数组的和分别为 $5$、$9$ 和 $1$。 再看第二个样例测试。在最优解中，第一个子数组包含前两个元素，第二个子数组只包含第三个元素。注意最后一个元素在本解中不属于任何子数组。 由 ChatGPT 4.1 翻译