josiftepe

Untitled

Nov 14th, 2020
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.44 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. int a[100000];
  5. int dp[100000];
  6.  
  7. int rec(int c){
  8.     if (c==n-1){
  9.         return 0;
  10.     }
  11.     if (dp[c]!=-1){
  12.         return dp[c];
  13.     }
  14.     else {
  15.     int dis;
  16.     int y=1e9;
  17.     for (int j=1;j<3;j++){
  18.         if (c+j<n){
  19.             dis=abs(a[c]-a[c+j]);
  20.             y=min(y,dis+rec(c+j));
  21.         }
  22.     }
  23.     dp [c]=y;
  24.     return y;
  25. }
  26. }
  27.  
  28. int main(){
  29.     cin>>n;
  30.     for (int i=0;i<n;i++){
  31.         cin>>a[i];
  32.         dp[i]=-1;
  33.     }
  34.     cout<<rec(0);
  35.    
  36.    
  37.    
  38.    
  39. }
Advertisement
Add Comment
Please, Sign In to add comment