Advertisement
Josif_tepe

Untitled

Sep 25th, 2022
766
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     ios_base::sync_with_stdio(true);
  8.     int n,k;
  9.     cin>>n>>k;
  10.     int x[n];
  11.     int dp[n + 1];
  12.     for(int i = 1; i <= n; i++) {
  13.         dp[i] = 2e9;
  14.     }
  15.     dp[0] = 0;
  16.     for(int i=0;i<n;i++)cin>>x[i];
  17.     for(int i=1;i<=k && i<n;i++)
  18.     {
  19.         dp[i]=abs(x[0]-x[i]);
  20.     }
  21.     for(int i=k;i<n;i++)
  22.     {
  23.         for(int j=1;j<=k;j++)
  24.         {
  25.                 dp[i]=min(dp[i], dp[i-j]+abs(x[i]-x[i-j]));
  26.            
  27.         }
  28.     }
  29.     cout<<dp[n-1];
  30.     return 0;
  31. }
  32.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement