青蛙跳石头 2 - 代码源竞赛平台

题目描述

蜗蜗在一条河边发现了 $N$ 块从左到右排列的石头，编号为 1 到 $N$。第 $i$ 块石头的高度为 $h_i$。

青蛙一开始位于第 1 块石头。从第 $i$ 块石头出发，每次可以跳到编号差在 $1$ 到 $K$ 之间的任意一块石头。青蛙从高度为 $x$ 的石头跳到高度为 $y$ 的石头，需要消耗 $|x-y|$ 点体力。

请你求出青蛙到达第 $N$ 块石头所需的最少体力。

输入格式

第一行包含两个整数 $N$ 和 $K$，分别表示石头数量和一次跳跃允许的最大编号差。

第二行包含 $N$ 个整数 $h_1,h_2,\ldots,h_N$，表示每块石头的高度。

输出格式

输出一行一个整数，表示最少体力消耗。

样例

5 3
10 30 40 50 20

30

样例解释

一种最优跳法是从第 1 块跳到第 2 块，再从第 2 块跳到第 5 块，体力消耗为 $|10-30|+|30-20|=30$。

数据范围

对于 100% 的数据，保证 $2\le N\le 10^5$，$1\le K\le 100$，$0\le h_i\le 10^4$。