Advertisement
Josif_tepe

Untitled

Nov 23rd, 2021
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.75 KB | None | 0 0
  1. #include <iostream>
  2. #include<cmath>
  3. using namespace std;
  4. int niza[1000005];
  5. int dp[100005];
  6. int n;
  7. int k;
  8. int mini(int a,int b)
  9. {
  10.     int m=0;
  11.     if(a<b)
  12.     {
  13.       m=a;
  14.     }else
  15.     {
  16.         m=b;
  17.     }
  18.     return m;
  19. }
  20. int f(int frog_at)
  21. {
  22.     if(frog_at==(n-1))
  23.     {
  24.         return 0;
  25.     }
  26.     if(dp[frog_at] != -1) {
  27.         return dp[frog_at];
  28.     }
  29.     int result=2e9;
  30.     for(int i=1;i<=k;i++)
  31.     {
  32.        if(frog_at+i<n)
  33.        {
  34.            result=mini(result,f(frog_at+i)+ abs(niza[frog_at]-niza[frog_at+i]));
  35.        }
  36.     }
  37.     return dp[frog_at] = result;
  38.  
  39. }
  40. int main()
  41. {
  42.     cin>>n>>k;
  43.     for(int i=0;i<n;i++)
  44.     {
  45.         cin>>niza[i];
  46.         dp[i] = -1;
  47.     }
  48.     cout<<f(0);
  49.     return 0;
  50. }
  51.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement