fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pb push_back
  5. #define yes cout<<"YES\n";
  6. #define no cout<<"NO\n";
  7. const int N=3e5+7;
  8. ll T=1;
  9. ll h[N];
  10. ll n, oo = 1e18;
  11. ll dp[N];
  12. ll rec(ll i)
  13. {
  14.     if(i > n)
  15.         return oo;
  16.     if(i == n)
  17.         return 0;
  18.  
  19.     if(dp[i] != -1)
  20.         return dp[i];
  21.  
  22.  
  23.     ll fp = rec(i + 1) + abs(h[i] - h[i + 1]);
  24.     ll sp = rec(i + 2) + abs(h[i] - h[i + 2]);
  25.  
  26.     dp[i] = min(fp, sp);
  27.  
  28.     return dp[i];
  29. }
  30. void solve()
  31. {
  32.     memset(dp, -1, sizeof dp);
  33.     cin >> n;
  34.     for(int i = 1; i <= n; i++)
  35.         cin >> h[i];
  36.     cout << rec(1);
  37. }
  38. int main()
  39. {
  40.     ios::sync_with_stdio(NULL);
  41.     cin.tie(0);
  42.     cout.tie(0);
  43.  
  44. //    freopen("","r", stdin);
  45. //    freopen("","w", stdout);
  46. //    cin>>T;
  47.     while(T--)
  48.         solve();
  49.     return 0;
  50. }
  51.  
Success #stdin #stdout 0.01s 6228KB
comments (?)
stdin
copy 
3
10 50 20
stdout
copy 
10
https://ideone.com/1U7nTu
language:
C++ (gcc 8.3)
created:
13 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!