2219 - 数字的选择-东方博宜OJ

题目描述

有 $n$ 个非负整数，请从这 $n$ 个非负整数中，选出 $m$ 个数，在不改变 $m$ 个数的顺序的情况下，构成一个新数列，要求该数列的中相邻两个数的差值绝对值的和尽可能小。

请问，这个最小的差值绝对值的和是多少？

比如：有 $5$ 个数是 $2$ $1$ $8$ $5$ $9$ ，如果从中选 $3$ 个数，不改变顺序的情况下，要求相邻 $2$ 个数的差值绝对值的和最小，选数方法可以是： $2$ $1$ $5$ ，差值绝对值的和是 $|1-2|+|5-1|=5$ 。

输入

第 $1$ 行输入 $2$ 个整数，分别是 $n$ 和 $m$ 。（ $2\leqm\leqn\leq100$ ）

第 $2$ 行，有 $n$ 个非负整数，数字之间用空格隔开。

输出

按题意输出最小的差值绝对值的和。（本题保证计算出来的结果，在int的范围内）

样例

5 3
2 1 8 5 9

来源

动态规划

标签

题目参数

上一题下一题