fork(1) download 
  1. #include <stdio.h>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. class FrogJump2 {
  8.  
  9. public:
  10.   int minimumCost(vector<int>& heights, int n, int k) {
  11.     if(n <= 1) return 0;
  12.  
  13.     vector<int> dp(n, 0);
  14.     dp[0] = 0;
  15.     dp[1] = abs(heights[0] - heights[1]);
  16.  
  17.     for(int i = 2; i < n; ++i) {
  18.       int cost = INT_MAX;
  19.       for(int j = max(0, i-k); j < i; ++j) {
  20.         cost = min(cost, dp[j] + abs(heights[i] - heights[j]));
  21.       }
  22.       dp[i] = cost;
  23.     }
  24.     return dp[n-1];
  25.   }
  26. };
  27.  
  28.  
  29. int main() {
  30.   int n, k;
  31.   cin >> n >> k;
  32.  
  33.   vector<int> heights(n);
  34.   for(int i = 0; i < n; ++i) cin >> heights[i];
  35.  
  36.   FrogJump2 *obj = new FrogJump2();
  37.   cout << obj->minimumCost(heights, n, k) << endl;
  38.  
  39.   return 0;
  40. }
  41.  
  42.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
10 4
40 10 20 70 80 10 20 70 80 60
stdout 
40
https://ideone.com/MEVk6s
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!