Frog 2
There are \(N\) stones, numbered \(1, 2, \dots, N\). The height of stone \(i\) is \(h_i\). A frog is on stone \(1\). From stone \(i\) it can jump to any of the stones \(i + 1, i + 2, \dots, i + K\). A jump from stone \(i\) to stone \(j\) costs \(|h_i - h_j|\).
Find the minimum total cost for the frog to reach stone \(N\).
Constraints:
- \(2 \le N \le 10^5\)
- \(1 \le K \le 100\)
- \(1 \le h_i \le 10^4\)
Input:
- First line: two integers \(N\) and \(K\).
- Second line: \(N\) integers \(h_1, h_2, \dots, h_N\).
Output:
- One integer — the minimum total cost.
Example:
Input:
5 3
10 30 40 50 20
Output:
30
(The frog jumps \(1 \to 2 \to 5\), with cost \(20 + 10 = 30\).)
Solution
This is Frog 1 with longer jumps. We use the same state:
\(dp_i\) = the minimum cost to reach stone \(i\) (stones are numbered from \(0\) in the code).
The last jump to stone \(i\) comes from one of the stones \(i - K, \dots, i - 1\) (only those that exist), so
\(dp_i = \min\limits_{\max(0, i - K) \le j < i} \left( dp_j + |h_i - h_j| \right)\)
with the base case \(dp_0 = 0\). We compute the values in increasing order of \(i\), because each value uses only smaller indices.
There are \(N\) states and each one checks at most \(K\) transitions, so the time complexity is \(O(N \cdot K)\), which is at most \(10^7\) operations.
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
int h[100000];
int dp[100000]; // dp[i] = minimum cost to reach stone i
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> h[i];
}
dp[0] = 0;
for (int i = 1; i < n; i++) {
dp[i] = 2000000000;
// the last jump comes from one of the stones i - k, ..., i - 1
for (int j = max(0, i - k); j < i; j++) {
dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));
}
}
cout << dp[n - 1] << "\n";
}