Dynamic Programming Practice 2
Submit solution
Points:
7
Time limit:
1.0s
Memory limit:
256M
Author:
Problem type
Allowed languages
Assembly, Awk, Brain****, C, C++, Java, Pascal, Perl, Python, Sed, Text
Mike starts at stone \(1\) and wishes to reach stone \(N\). Mike can jump up to \(K\) stones forward. Each stone \(i\) has a height \(h_{i}\). The cost for jumping between stones \(i\) and \(j\) is \(|h_{i} - h_{j}|\). Help Mike find the minimum cost needed to reach stone \(N\).
Constraints
\(1 \leq N \leq 10^{4}\)
\(1 \leq K \leq 100\)
\(1 \leq h_{i} \leq 10^{3}\)
Input Specification
The first line contains two integers, \(N\) and \(K\).
The second line contains \(N\) integers, \(h_{i}\).
Output Specification
Output one integer, the minimum cost.
Sample Input
5 3
1 3 4 5 2
Sample Output
3
Explaination for Sample Output
The optimal path is through stones \(1\), \(2\), and \(5\). This incurs a cost of \(|h_1 - h_2| + |h_2 - h_5| = |1 - 3| + |3 - 2| = 2 + 1 = 3\). It can be shown that a lower cost is impossible.
Comments