Educational DP Contest AtCoder B - Frog 2

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 1G

Problem type

There are N stones, numbered 1,2,,N. For each i (1iN), the height of Stone i is hi.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone N:

  • If the frog is currently on Stone i, jump to one of the following: Stone i+1,i+2,,i+K. Here, a cost of |hihj| is incurred, where j is the stone to land on.

Find the minimum possible total cost incurred before the frog reaches Stone N.

Constraints

  • All values in input are integers.
  • 2N105
  • 1K100
  • 1hi104

Input Specification

The first line of input will contain 2 integers N and K.

The second line of input will contain N spaced integers, hi, the height of stone i.

Output Specification

Output a single integer, the minimum possible total cost incurred.

Sample Input 1

Copy
5 3
10 30 40 50 20

Sample Output 1

Copy
30

Sample Input 2

Copy
3 1
10 20 10

Sample Output 2

Copy
20

Sample Input 3

Copy
2 100
10 10

Sample Output 3

Copy
0

Sample Input 4

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

Sample Output 4

Copy
40

Sample Explanations

For the first sample, if we follow the path 125, the total cost incurred would be |1030|+|3020|=30.

For the second sample, if we follow the path 123, the total cost incurred would be |1020|+|2010|=20.

For the third sample, if we follow the path 12, the total cost incurred would be |1010|=0.

For the fourth sample, if we follow the path 14810, the total cost incurred would be |4070|+|7070|+|7060|=40.


Comments


  • -1
    AndyZhang68  commented on June 17, 2024, 3:40 a.m.

    pypy is recommended for python submissions to not TLE