310529: CF1847A. The Man who became a God
Description
Kars is tired and resentful of the narrow mindset of his village since they are content with staying where they are and are not trying to become the perfect life form. Being a top-notch inventor, Kars wishes to enhance his body and become the perfect life form. Unfortunately, $n$ of the villagers have become suspicious of his ideas. The $i$-th villager has a suspicion of $a_i$ on him. Individually each villager is scared of Kars, so they form into groups to be more powerful.
The power of the group of villagers from $l$ to $r$ be defined as $f(l,r)$ where
$$f(l,r) = |a_l - a_{l+1}| + |a_{l + 1} - a_{l + 2}| + \ldots + |a_{r-1} - a_r|.$$
Here $|x-y|$ is the absolute value of $x-y$. A group with only one villager has a power of $0$.
Kars wants to break the villagers into exactly $k$ contiguous subgroups so that the sum of their power is minimized. Formally, he must find $k - 1$ positive integers $1 \le r_1 < r_2 < \ldots < r_{k - 1} < n$ such that $f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$ is minimised. Help Kars in finding the minimum value of $f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$.
InputThe first line contains a single integer $t$ $(1 \leq t \leq 100)$ — the number of test cases. The description of test cases follows.
The first line of each test case contains two integers $n,k$ $(1 \leq k \leq n \leq 100)$ — the number of villagers and the number of groups they must be split into.
The second line of each test case contains $n$ integers $a_1,a_2, \ldots, a_n$ $(1 \leq a_i \leq 500)$ — the suspicion of each of the villagers.
OutputFor each test case, output a single integer — the minimum possible value of sum of power of all the groups i. e. the minimum possible value of $f(1,r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$.
ExampleInput3 4 2 1 3 5 2 6 3 1 9 12 4 7 2 12 8 1 9 8 2 3 3 1 8 7 7 9 2Output
4 11 2Note
In the first test case, we will group the villagers with suspicion $(1,3,5,2)$ into $(1,3,5)$ and $(2)$. So, $f(1,3) + f(4,4) = (|1 - 3| + |3 - 5|) + 0 = 4 + 0 = 4$.
In the second test case, we will group the villagers with suspicion $(1,9,12,4,7,2)$ into $(1),(9,12),(4,7,2)$. So, $f(1,1) + f(2,3) + f(4,6) = 0 + 3 + 8 = 11$.
Input
题意翻译
给定一个数组 $\{x_1,x_2,\cdots,x_n\}$ 和一个整数 $k$，记 $f(l,r)=\sum_{i=0}^{i \le r-l} |x_{l+i}-x_{l+i+1}|$，求将数组划分为 $k$ 个部分的划分方案，使得对每个部分的 $f(l,r)$ 之和最小. 翻译 @[zymooll](https://www.luogu.com.cn/user/289296)Output
卡尔对村里人的狭隘思维感到疲倦和不满，因为他们满足于停滞不前，不想成为完美的生命形态。作为一名顶尖发明家，卡尔希望增强自己的身体，成为完美的生命形态。不幸的是，村里的n个人开始怀疑他的想法。第i个村民对他的怀疑度为a_i。每个村民单独都害怕卡尔，所以他们组成小组以变得更强。
定义从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。
卡尔想将村民分成恰好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) $最小化。帮助卡尔找到$ f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n) $的最小值。
输入数据格式：
第一行包含一个整数t（1≤t≤100）——测试用例的数量。接下来是t个测试用例的描述。
每个测试用例的第一行包含两个整数n和k（1≤k≤n≤100）——村民的数量和必须将他们分成的组数。
每个测试用例的第二行包含n个整数$ a_1, a_2, \ldots, a_n $（1≤a_i≤500）——每个村民的怀疑度。
输出数据格式：
对于每个测试用例，输出一个整数——所有组的权力之和的最小可能值，即$ f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n) $的最小可能值。题目大意： 卡尔对村里人的狭隘思维感到疲倦和不满，因为他们满足于停滞不前，不想成为完美的生命形态。作为一名顶尖发明家，卡尔希望增强自己的身体，成为完美的生命形态。不幸的是，村里的n个人开始怀疑他的想法。第i个村民对他的怀疑度为a_i。每个村民单独都害怕卡尔，所以他们组成小组以变得更强。 定义从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。 卡尔想将村民分成恰好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) $最小化。帮助卡尔找到$ f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n) $的最小值。 输入数据格式： 第一行包含一个整数t（1≤t≤100）——测试用例的数量。接下来是t个测试用例的描述。 每个测试用例的第一行包含两个整数n和k（1≤k≤n≤100）——村民的数量和必须将他们分成的组数。 每个测试用例的第二行包含n个整数$ a_1, a_2, \ldots, a_n $（1≤a_i≤500）——每个村民的怀疑度。 输出数据格式： 对于每个测试用例，输出一个整数——所有组的权力之和的最小可能值，即$ f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n) $的最小可能值。