josiftepe

Untitled

Nov 14th, 2020
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.64 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 array[100000];
  7. int dp[1000000];
  8. int k,n;
  9. int rec(int a)
  10. {
  11.     if (a==n-1)
  12.     {
  13.         return 0;
  14.     }
  15.     if (dp[a]!=-1)
  16.     {
  17.         return dp[a];
  18.     }
  19.  
  20.     int y=1e9;
  21.     for (int j=1;j<=k;j++)
  22.     {     if (a+j<n)
  23.         { y=min(y, abs(array[a]-array[a+j]) + rec (a+j) );
  24.     } }
  25.     dp[a]=y;
  26.     return y;
  27. }
  28.  
  29.  
  30.  
  31. int main()
  32. {
  33.  
  34.    cin>>n>>k;
  35.    for (int i=0;i<n;i++)
  36.    {
  37.        cin>>array[i];
  38.    }
  39.  
  40.    for (int i=0;i<1e6;i++)
  41.    {
  42.        dp[i]=-1;
  43.    }
  44.    cout<<rec(0);
  45.     return 0;
  46. }
  47.  
Advertisement
Add Comment
Please, Sign In to add comment