AT_dp_b Frog 2

题目描述

有 $N$ 个台阶。每个台阶编号为 $1, 2, \ldots, N$。对于每个 $i$（$1 \leq i \leq N$），第 $i$ 个台阶的高度为 $h_i$。

一只青蛙最初站在第 $1$ 个台阶上。青蛙可以多次进行如下操作，试图到达第 $N$ 个台阶：

• 当青蛙在第 $i$ 个台阶时，可以跳到第 $i+1, i+2, \ldots, i+K$ 中的任意一个台阶。假设跳到第 $j$ 个台阶，则需要支付的代价为 $|h_i - h_j|$。

请你求出青蛙到达第 $N$ 个台阶所需支付的总代价的最小值。

输入格式

输入以如下格式从标准输入读入：

$N$ $K$ $h_1$ $h_2$ $\ldots$ $h_N$

输出格式

输出青蛙需要支付的总代价的最小值。

输入输出样例 #1

输入 #1

5 3
10 30 40 50 20

输出 #1

30

输入输出样例 #2

输入 #2

3 1
10 20 10

输出 #2

20

输入输出样例 #3

输入 #3

2 100
10 10

输出 #3

0

输入输出样例 #4

输入 #4

10 4
40 10 20 70 80 10 20 70 80 60

输出 #4

40

说明/提示

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 10^5$
• $1 \leq K \leq 100$
• $1 \leq h_i \leq 10^4$

样例解释 1

如果青蛙依次跳到台阶 $1 \to 2 \to 5$，总代价为 $|10 - 30| + |30 - 20| = 30$。

样例解释 2

如果青蛙依次跳到台阶 $1 \to 2 \to 3$，总代价为 $|10 - 20| + |20 - 10| = 20$。

样例解释 3

如果青蛙直接跳到台阶 $1 \to 2$，总代价为 $|10 - 10| = 0$。

样例解释 4

如果青蛙依次跳到台阶 $1 \to 4 \to 8 \to 10$，总代价为 $|40 - 70| + |70 - 70| + |70 - 60| = 40$。

由 ChatGPT 4.1 翻译