josiftepe

Untitled

Nov 14th, 2020
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.61 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int maxn = 1e5 + 10;
  5. const int INF = 2e9 + 5;
  6. int main()
  7. {
  8.     int n,k;
  9.     cin>>n>>k;
  10.     int array[n+1];
  11.     for (int i=0;i<n;i++)
  12.     {
  13.         cin>>array[i];
  14.     }
  15.  
  16.     int dp[n+1];
  17.     for (int i=0;i<n+1;i++)
  18.     {
  19.         dp[i]=2e9;
  20.     }
  21.     int i=1;
  22.     dp[0]=0;
  23.     for (int a=0;a<n;a++)
  24.     {
  25.         for (int i=1;i<=k;i++)
  26.         {
  27.             if (a-i>=0)
  28.             {
  29.                 dp[a]=min(dp[a], abs(array[a]-array[a-i]) + dp[a-i] );
  30.             }
  31.         }
  32.     }
  33.     cout<<dp[n-1]<<endl;
  34.     return 0;
  35. }
  36.  
Advertisement
Add Comment
Please, Sign In to add comment