10704: Жаба - 2


Відправити розв'язок

Бали: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Brain****, C++, Java, Pascal, Python, v8js

Є \(N\) каменів пронумерованих від \(1\) до \(N\). Для кожного каменя відома його висота \(Hi\).

Жаба початково знаходиться на камені номер \(1\) і хоче дострибати на камінь номер \(N\).

Якщо жаба знаходиться на камені \(i\) вона може стрибнути на камінь \(i+1\) або \(i+2\) або ...\(i+K\) (добто не довше ніж на \(K\) каменів).
Ціна стрибка з каменя \(i\) на камінь \(j\) - модуль різниць висот цих каменів \(|Hi-Hj|\)

Знайдіть найдешевшу ціну за яку жаба може дістатись каменя номер \(N\)

Формат вхідних даних

В першому рядку два цілі числа \(N,K\) (\(1 \le N \le 10^5\), \(1 \le K \le 100\))
В наступному рядку \(N\) цілих чисел \(Hi\) - висоти каменів (\(1 \le Hi \le 10^4\)).

Формат вихідних даних

Виведіть наменшу можливу ціну.

Приклад вхідних даних-1

5 3
10 30 40 50 20

Приклад вихідних даних-1

30

Пояснення до прикладу-1

Існує такий шлях 1 - 2 - 5, з ціною |10−30| + |30−20| = 30.

Приклад вхідних даних-2

3 1
10 20 10

Приклад вихідних даних-2

20

Пояснення до прикладу-2

Існує такий шлях 1 - 2 - 3, з ціною |10−20| + |20−10| = 20

Приклад вхідних даних-3

2 100
10 10

Приклад вихідних даних-3

0

Приклад вхідних даних-4

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

Приклад вихідних даних-4

40

Пояснення до прикладу-4

Існує такий шлях 1 - 4 - 8 - 10, з ціною |40−70| + |70−70| + |70-60| = 40

Коментарі

Ще немає коментарів.