fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define  ll  long long
  4. #define  nl '\n'
  5. #define  int long long
  6.  
  7. void file()
  8. {
  9. #ifndef ONLINE_JUDGE
  10.     freopen("in.txt", "r", stdin);
  11.     freopen("out.txt", "w", stdout);
  12. #else
  13.     // freopen("input.txt", "r", stdin);
  14.     // freopen("output.txt", "w", stdout);
  15. #endif
  16. }
  17.  
  18. int dp[100005][2], vis[100005][2], id = 1, n;
  19. vector<int> v;
  20. int rec(int i,int f)
  21. {
  22.     if (i >= n - 1)
  23.         return 0;
  24.  
  25.     int &ret = dp[i][f];
  26.     if (vis[i][f] == id)return ret;
  27.     vis[i][f] = id;
  28.     ret = rec(i + 2,f) + max({0ll, v[i - 1] - v[i] + 1, v[i + 1] - v[i] + 1});
  29.     if (i+1 < n-1 && f)
  30.         ret = min(ret,rec(i+1,0));
  31.     return ret;
  32. }
  33.  
  34. void solve()
  35. {
  36.  
  37.     cin >> n;
  38.  
  39.     v = vector<int> (n);
  40.     for (int i = 0; i < n; i++)
  41.         cin >> v[i];
  42.  
  43.     int res = 0;
  44.     for (int i = 1; i < n - 1; i += 2)
  45.     {
  46.         res += max({0ll, v[i - 1] - v[i] + 1, v[i + 1] - v[i] + 1});
  47.     }
  48.  
  49.     if (n % 2 == 0)
  50.     {
  51.         res = min(res, rec(1,1));
  52.     }
  53.     cout << res << nl;
  54.     id++;
  55. }
  56.  
  57. signed main()
  58. {
  59.     ios::sync_with_stdio(0);
  60.     cin.tie(0);
  61.     cout.tie(0);
  62.     file();
  63.  
  64.     int t = 1;
  65.     cin >> t;
  66.     while (t--)
  67.     {
  68.         solve();
  69.     }
  70.  
  71.     return 0;
  72. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/pWTtdx
language:
C++14 (gcc 8.3)
created:
4 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!