Advertisement
LEGEND2004

Frog 2

Aug 24th, 2023
932
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.56 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. const int INF = 1e9;
  6. const int mod = 1e9 + 7;
  7. const int N = 1e6 + 5;
  8. int dp[N];
  9.  
  10. signed main()
  11. {
  12.     int n , k;
  13.     cin >> n >> k;
  14.     int a[n + 5];
  15.     for(int i = 1; i <= n; i++){
  16.         cin >> a[i];
  17.     }
  18.     dp[1] = 0;
  19.     for(int i = 2; i <= n; i++){
  20.         dp[i] = INF;
  21.         for(int j = 1; j <= k; j++){
  22.             if(i == j)
  23.                 break;
  24.             dp[i] = min(dp[i] , dp[i - j] + abs(a[i] - a[i - j]));
  25.         }
  26.     }
  27.     cout << dp[n] << endl;
  28. }
  29.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement