Frog 2 – Atcode DP

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 1e5;
const int MAX_H = 1e4;

int n, k;
int h[MAX_N];
int memo[MAX_N];

int dp(int i) {
    if (i == 0) {
        return 0;
    }

    if (memo[i] != -1) {
        return memo[i];
    }

    int result = MAX_N * MAX_H;
    for (int j = 1; j <= k && i - j >= 0; ++j) {
        result = min(result, dp(i - j) + abs(h[i] - h[i - j]));
    }

    memo[i] = result;
    return memo[i];
}

int main() {
    cin >> n >> k;

    memset(memo, -1, sizeof(memo));

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

    cout << dp(n - 1);

    return 0;
}

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 1e5;
const int MAX_H = 1e4;

int n, k;
int h[MAX_N];
int memo[MAX_N];
int trace[MAX_N];

int dp(int i) {
    if (i == 0) {
        return 0;
    }

    if (memo[i] != -1) {
        return memo[i];
    }

    int result = MAX_N * MAX_H;
    for (int j = 1; j <= k && i - j >= 0; ++j) {
        int cost = dp(i - j) + abs(h[i] - h[i - j]);
        if (result > cost) {
            result = cost;
            trace[i] = i - j;
        }
    }

    memo[i] = result;
    return memo[i];
}

void printTrace() {
    vector<int> path;

    int current = n - 1;
    while (current != -1) {
        path.push_back(current);
        current = trace[current];
    }

    for (int i = path.size() - 1; i >= 0; --i) {
        cout << path[i] + 1 << " ";
    }
}

int main() {
    cin >> n >> k;

    memset(memo, -1, sizeof(memo));
    memset(trace, -1, sizeof(trace));

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

    cout << dp(n - 1) << endl;
    printTrace();

    return 0;
}