Dynamic Programming with Path Restoring (DP with Path Restoring)

Dynamic Programming with Path Restoring (DP with Path Restoring) - Preparation to IOI Part 2

1. Function restore_path():
   1.1. Create an empty list path.
   1.2. Set cur = n.
   1.3. While cur != 0:
        1.3.1. Add cur to path.
        1.3.2. Set cur = parent[cur].
   1.4. Reverse path.
   1.5. Return path.

2. Function main():
   2.1. Read n and the heights h[1], h[2], ..., h[n].
   2.2. Set dp[1] = 0 and parent[1] = 0.
   2.3. If n >= 2:
        2.3.1. Set dp[2] = abs(h[2] - h[1]).
        2.3.2. Set parent[2] = 1.
   2.4. For each i from 3 to n:
        2.4.1. Let x = dp[i - 1] + abs(h[i] - h[i - 1]).
        2.4.2. Let y = dp[i - 2] + abs(h[i] - h[i - 2]).
        2.4.3. If x <= y:
               2.4.3.1. Set dp[i] = x and parent[i] = i - 1.
        2.4.4. Otherwise:
               2.4.4.1. Set dp[i] = y and parent[i] = i - 2.
   2.5. Let path = restore_path().
   2.6. Output dp[n].
   2.7. Output the size of path and all its stones.

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

int n;
long long h[N];
long long dp[N];
int parent[N];

vector<int> restore_path() {
    vector<int> path;
    int cur = n;
    while (cur != 0) {
        path.push_back(cur);
        cur = parent[cur];
    }
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    dp[1] = 0;
    parent[1] = 0;

    if (n >= 2) {
        dp[2] = abs(h[2] - h[1]);
        parent[2] = 1;
    }

    for (int i = 3; i <= n; i++) {
        long long x = dp[i - 1] + abs(h[i] - h[i - 1]);
        long long y = dp[i - 2] + abs(h[i] - h[i - 2]);

        dp[i] = x;
        parent[i] = i - 1;

        if (y < dp[i]) {
            dp[i] = y;
            parent[i] = i - 2;
        }
    }

    vector<int> path = restore_path();
    int k = path.size();

    cout << dp[n] << endl;
    cout << k << endl;
    for (int i = 0; i < k; i++) {
        cout << path[i];
        if (i + 1 == k) {
            cout << endl;
        } else {
            cout << ' ';
        }
    }

    return 0;
}

Dynamic Programming with Path Restoring (DP with Path Restoring)

Introduction

The new information we store

Main algorithm

Restoration walkthrough

General pattern

Implementation

Complexity