提出 #54289370

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;
int n, k;
int t[(int)1e5 + 1];

int frogJump(vector<int>& a, int n, int k) {
    if (n == 1) return 0; // Starting point, no cost

    if (t[n] != -1) return t[n];

    int minCost = INT_MAX;
    for (int i = 1; i <= k; ++i) {
        if (n - i >= 1) {
            minCost = min(minCost, frogJump(a, n - i, k) + abs(a[n - 1] - a[n - i - 1]));
        }
    }
    t[n] = minCost % mod;
    return t[n];
}

int main() {
    memset(t, -1, sizeof(t));

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

    int result = frogJump(a, n, k);
    cout << result << endl;
    return 0;
}

提出情報

ジャッジ結果