2219 - 数字的选择

题目描述

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

请问,这个最小的差值绝对值的和是多少?

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

输入

1 行输入 2 个整数,分别是 nm 。(2≤m≤n≤100

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

输出

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

样例

输入

5 3
2 1 8 5 9 

输出

5
来源

动态规划

标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 132
通过人数 80
金币数量 2 枚
难度 基础


上一题 下一题