1. Идея

Нужно найти минимальную суммарную стоимость пути от первого камня до последнего.

Естественная идея — динамическое программирование.

Будем хранить dp[i] — минимальное усилие, нужное, чтобы попасть на камень i.

Тогда, чтобы прийти на камень i, лягушка могла прыгнуть на него с одного из предыдущих камней:

• i - 1
• i - 2
• ...
• i - K

если такие индексы существуют.

Если последний прыжок был с камня j на камень i, то стоимость такого варианта равна:

dp[j] + |h[i] - h[j]|

Значит, надо перебрать все допустимые j и взять минимум.

2. Наблюдения

1. На первый камень лягушка уже стоит, поэтому: dp[0] = 0.

2. Для каждого камня i достаточно смотреть только на последние K камней перед ним, потому что прыгать дальше, чем на K, нельзя.

3. Ограничение K <= 100 очень важно: даже если n большое, перебор до 100 вариантов для каждого камня вполне подходит.

4. Ответ может быть большим, поэтому нужно использовать 64-битные целые числа:

   • в C++ это long long,
   • в Python проблем нет, там целые числа длинные автоматически.

3. Алгоритм

1. Считать n, K и массив высот h.
2. Создать массив dp длины n, заполненный большим числом.
3. Положить dp[0] = 0.
4. Для каждого камня i от 1 до n - 1:
   • найти левую границу: left = max(0, i - K)
   • перебрать все j от left до i - 1
   • посчитать стоимость перехода: dp[j] + abs(h[i] - h[j])
   • обновить минимум для dp[i]
5. Вывести dp[n - 1].

4. Почему это работает

Докажем, что такой переход действительно находит оптимальный ответ.

Рассмотрим некоторый камень i. Любой путь в i заканчивается прыжком с какого-то камня j, где i - K <= j < i, потому что длина прыжка не может превышать K.

Если мы уже знаем минимальную стоимость добраться до j, то стоимость пути в i через j равна:

dp[j] + |h[i] - h[j]|

Среди всех допустимых последних камней j нужно выбрать тот, который дает минимальную сумму. Значит,

dp[i] — это минимум по всем таким j.

Почему этого достаточно?

• любой допустимый путь в i обязательно имеет некоторый последний прыжок;
• для этого последнего прыжка мы рассматриваем соответствующий j;
• стоимость лучшего пути до j уже хранится в dp[j];
• значит, минимум по всем таким вариантам и есть оптимальный ответ для i.

Так как мы считаем dp слева направо, то в момент вычисления dp[i] все нужные значения dp[j] уже известны.

Следовательно, после заполнения массива dp значение dp[n - 1] равно минимальному суммарному усилию до последнего камня.

5. Сложность

Для каждого камня перебирается не более K предыдущих камней.

Итоговая сложность:

• O(n * K)

Память:

• O(n)

При n <= 10^5 и K <= 100 это работает быстро.

6. Код на C++17

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>

using namespace std;

int main() {
    int n, K;
    cin >> n >> K;

    vector<long long> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    const long long INF = LLONG_MAX / 4;
    vector<long long> dp(n, INF);
    dp[0] = 0;

    for (int i = 1; i < n; i++) {
        int left = max(0, i - K);
        for (int j = left; j < i; j++) {
            long long cost = dp[j] + llabs(h[i] - h[j]);
            if (cost < dp[i]) {
                dp[i] = cost;
            }
        }
    }

    cout << dp[n - 1] << '\n';
    return 0;
}

7. Код на Python 3

n, K = map(int, input().split())
h = list(map(int, input().split()))

INF = 10**30
dp = [INF] * n
dp[0] = 0

for i in range(1, n):
    left = max(0, i - K)
    best = INF
    for j in range(left, i):
        cost = dp[j] + abs(h[i] - h[j])
        if cost < best:
            best = cost
    dp[i] = best

print(dp[n - 1])