CF1847A The Man who became a God

Kars 厌倦并且对村庄里人们的狭隘思想感到不满，因为他们满足于现状，并不试图成为完美的生命体。作为一名顶尖的发明家，Kars 希望增强自己的身体，成为完美的生命体。不幸的是，村庄里的 $n$ 个村民开始对他的想法产生怀疑。第 $i$ 个村民对他有 $a_i$ 的怀疑度。每个村民单独面对 Kars 时都很害怕，于是他们会组成小组来增强力量。 从第 $l$ 个村民到第 $r$ 个村民组成的小组的力量定义为 $f(l,r)$，其中 $$ f(l,r) = |a_l - a_{l+1}| + |a_{l + 1} - a_{l + 2}| + \ldots + |a_{r-1} - a_r| $$ 这里 $|x-y|$ 表示 $x-y$ 的绝对值。只有一个村民的小组力量为 $0$。 Kars 想要将村民恰好分成 $k$ 个连续的小组，使得所有小组力量之和最小。形式化地，他需要找到 $k-1$ 个正整数 $1 \le r_1 < r_2 < \ldots < r_{k-1} < n$，使得 $f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$ 的值最小。请帮助 Kars 求出 $f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$ 的最小值。

第一行包含一个整数 $t$ $(1 \leq t \leq 100)$，表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n, k$ $(1 \leq k \leq n \leq 100)$，分别表示村民的数量和需要分成的小组数。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 500)$，表示每个村民的怀疑度。

对于每个测试用例，输出一个整数，表示所有小组力量之和的最小可能值，即 $f(1,r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$ 的最小值。

在第一个测试用例中，我们将怀疑度为 $(1,3,5,2)$ 的村民分为 $(1,3,5)$ 和 $(2)$ 两组。于是 $f(1,3) + f(4,4) = (|1 - 3| + |3 - 5|) + 0 = 4 + 0 = 4$。 在第二个测试用例中，我们将怀疑度为 $(1,9,12,4,7,2)$ 的村民分为 $(1),(9,12),(4,7,2)$ 三组。于是 $f(1,1) + f(2,3) + f(4,6) = 0 + 3 + 8 = 11$。 由 ChatGPT 4.1 翻译