小石腳受傷了,但他被困在湖中央,要出去只能靠一排 $N$ 個橫向等間距、高低不同的石頭。這 $N$ 個石頭分別具有高度 $h_1, h_2, \dots, h_N$。
小石在編號 $1$ 的石頭上,他必須跳到編號 $N$ 的石頭上才算逃脫。因為他的腳傷,他縱向跳躍時會感到不適,但橫向則不會。他在一次從第 $i$ 個石頭到第 $j$ 個石頭的跳躍中感受到的不適值是 $|h_i - h_j|$。然而他也有跳躍距離限制,當他在石頭 $i$ 時,他只能跳到石頭 $i+1, i+2,\dots, i+K$ 上。他整段路的不適值是所有跳躍不適值的加總。
對於給定的 $N,K$ 和石頭高度 $h_1, h_2, \dots, h_N$,請你求出最小可能的不適值為何。
輸入第一行是兩個以空白分隔的整數,分別代表 $N, K$。
輸入第二行是 $N$ 個以空白分隔的整數,代表 $h_1, h_2, \dots, h_N$。
輸入保證 $1\le N\le 10^ 5$,$1\le K\le 100$,$1\le h_i\le 10^ 9$。
輸出一行一個整數,代表最小走完這段路的不適值。
Atcoder Educational DP Contest
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~15 | 無額外限制 | 100 |