TopCoder

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

50.0% (6/12)

Tags

Description

小石腳受傷了,但他被困在湖中央,要出去只能靠一排 N 個橫向等間距、高低不同的石頭。這 N 個石頭分別具有高度 h1,h2,,hN

小石在編號 1 的石頭上,他必須跳到編號 N 的石頭上才算逃脫。因為他的腳傷,他縱向跳躍時會感到不適,但橫向則不會。他在一次從第 i 個石頭到第 j 個石頭的跳躍中感受到的不適值是 |hihj|。然而他也有跳躍距離限制,當他在石頭 i 時,他只能跳到石頭 i+1,i+2,,i+K 上。他整段路的不適值是所有跳躍不適值的加總。

對於給定的 N,K 和石頭高度 h1,h2,,hN,請你求出最小可能的不適值為何。

Input Format

輸入第一行是兩個以空白分隔的整數,分別代表 N,K

輸入第二行是 N 個以空白分隔的整數,代表 h1,h2,,hN

輸入保證 1N1051K1001hi109

Output Format

輸出一行一個整數,代表最小走完這段路的不適值。

Sample Input 1

5 2
1 5 3 4 6

Sample Output 1

5

Sample Input 2

7 1
1 5 4 3 2 6 7

Sample Output 2

12

Hints

Problem Source

Atcoder Educational DP Contest

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~15 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2