fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef vector<int> vi;
  6. typedef vector<long long> vl;
  7. #define pb push_back
  8. #define ff first
  9. #define ss second
  10. #define forn(n) for (int i = 0; i < n; i++)
  11. #define forc(cn, abc) ((cn).find(abc) != (cn).end())
  12. #define yes cout << "YES\n";
  13. #define no cout << "NO\n";
  14. #define all(a) a.begin(), a.end()
  15. #define rall(a) a.rbegin(), a.rend()
  16. #define poin(x) cout << fixed << setprecision(x);
  17.  
  18. vector<ll> dp(100005, 1e18), h(100005);
  19.  
  20. ll f(ll x)
  21. {
  22.     if (x == 0)
  23.         return 0;
  24.  
  25.     if (dp[x] != 1e18)
  26.     {
  27.         return dp[x];
  28.     }
  29.  
  30.     ll costfromX1 = f(x - 1) + abs(h[x] - h[x - 1]);
  31.  
  32.     if (x == 1)
  33.         return costfromX1;
  34.  
  35.     ll costfromX2 = f(x - 2) + abs(h[x] - h[x - 2]);
  36.  
  37.     return dp[x] = min(costfromX1, costfromX2);
  38. }
  39.  
  40. int main()
  41. {
  42.     ios_base::sync_with_stdio(0);
  43.     cin.tie(0);
  44.  
  45.     int n;
  46.     cin >> n;
  47.  
  48.     forn(n)
  49.     {
  50.         cin >> h[i];
  51.     }
  52.  
  53.     cout << f(n - 1) << endl;
  54.  
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
4
10 30 40 20
stdout
copy 
30
https://ideone.com/Zv6VIJ
language:
C++ (gcc 8.3)
created:
21 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!