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
Коментарі