Skip to content

14129: 【原4129】K单调

题目

题目描述

author: 黄俊翔 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4129 ## Description

求把给定数列变为一个k单调数列的最小代价。以下是定义。

单调数列:严格上升或严格下降的连续数列。

k单调数列:可以被划分为不重叠的k段各自“严格上升或严格下降的连续数列”的连续数列(可以第一段上升第二段下降。任意一个长度为n的单调数列可以被随意划分为若干个i单调数列,i=1~n)。

代价:\(\sum(|(a[i]-b[i])|)\)。其中a是给定数列,b是最佳目标数列(不需要具体求出,只需要最小代价)。

Input Format

第一行一个整数\(T\),为数据组数。

接下来\(T\)组数据,每组数据两行。

每组数据的第一行为两个正整数\(N,M\),代表数列的长度和目标是把原数列变为M单调数列。

每组数据的第二行为\(N\)个正整数,代表给定数列\(a\)。

Output Format

有\(T\)组输出,对应T组输入。

每组数据输出1个正整数,代表最小代价。

Sample Input

4
4 1
1 1 1 1
4 2
1 1 1 1
4 4
1 1 1 1
6 1
1 2 3 3 2 1

Sample Output

4
2
0
9

Data Range

对于\(30\%\)的数据,\(N \le 10, M = 1\)。

对于\(60\%\)的数据,\(M = 1\)。

对于\(100\%\)的数据,\(1 \le T \le 5, 1 \le N \le 1000, 1 \le M \le 10\, -100000 \le a[i] \le 100000)\)。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!