Advertisement
Josif_tepe

Untitled

Apr 6th, 2022
1,082
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.68 KB | None
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <math.h>
  5. #include <vector>
  6. #include <queue>
  7. using namespace std;
  8. int n, k;
  9. int arr[100005];
  10. int dp[100005];
  11. int frog(int i) {
  12.     if(i >= n - 1) {
  13.         return 0;
  14.     }
  15.     if(dp[i] != -1) {
  16.         return dp[i];
  17.     }
  18.     int result = 2e9;
  19.     for(int j = 1; j <= k; j++) {
  20.         if(i + j < n) {
  21.             result = min(result, frog(i + j) + abs(arr[i] - arr[i + j]));
  22.         }
  23.     }
  24.    
  25.     return dp[i] = result;
  26. }
  27. int main()
  28. {
  29.     cin >> n >> k;
  30.     for(int i = 0; i < n; i++) {
  31.         cin >> arr[i];
  32.     }
  33.     memset(dp, -1, sizeof dp);
  34.     cout << frog(0) << endl;
  35.     return 0;
  36. }
  37.  
Advertisement
RAW Paste Data Copied
Advertisement