fork download
copy 
  1. // Source: https://u...content-available-to-author-only...o.guide/general/io
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. using ll = long long int;
  6. #define FOR(i,a,b) for(int i = a; i < b; i++)
  7. void solve(){
  8.     int n;
  9.     cin >> n;
  10.     vector <ll> l1(n); FOR(i,0,n) cin >> l1[i]; 
  11.     vector <ll> dp(n,1000000000000000LL); vector <ll> appear(n,-1);
  12.     vector <bool> good(n, false);
  13.     // dp[i] = cost to remove i, when remove i the fall damage go 
  14.     // directly on top of the one on I, and we could
  15.     // 1. link to the next number more than 1 cost
  16.     // 2. link it directly to the cost of the that number. 
  17.     // we should only link directly to the cost of that number if on top of it is a 1
  18.     // or if it is the last one.
  19.     for (int i = n -2; i >= 0; i --){
  20.         appear[i] = (l1[i+1] >1 ? i + 1 : appear[i+1]);
  21.     }
  22.     for (int i = n-1; i >= 0; i--){
  23.         good[i] = (i == n-1 || l1[i+1] == 1);
  24.     }
  25.     dp[n-1] = l1[n-1];
  26.     for (int i =n -2; i >= 0; i--){
  27.         dp[i] = dp[i+1] + l1[i];
  28.         ll v = l1[i] + max(0LL, l1[i+1] - (i + 1));
  29.         if (appear[i+1] == -1){
  30.             dp[i] = min(dp[i], v);
  31.             // cout << dp[i] << " ";
  32.             continue;
  33.         }
  34.         if (appear[i+1] == i + 2){
  35.             ll g = v;
  36.             v += dp[i+2]; 
  37.             if (good[appear[i+1]]){
  38.                 v = min(v, g + dp[appear[i+1]] - 1);
  39.             }
  40.             v = min(v, g + dp[appear[i + 1]]);
  41.             if (i + 3 < n){
  42.                 v = min(v, g + l1[i+2] - 1 + dp[i+3]);
  43.             }
  44.         }
  45.         else{
  46.             ll g = v;
  47.             v = g + min(dp[i+2], dp[appear[i+1] - 1]);
  48.             if (good[appear[i+1]]){
  49.                 v = min(v, g + dp[appear[i+1]] - 1);
  50.             }
  51.             v = min(v, g + dp[appear[i + 1]]);
  52.         }
  53.         dp[i] = min(dp[i], v);
  54.         // cout << dp[i] << " ";
  55.     }
  56.     // cout << "\n";
  57.     cout << dp[0] << "\n";
  58. }
  59. int main() {
  60. 	int t;
  61.     cin >> t;
  62.     while (t--) solve();
  63.     return 0;
  64. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RHwYnL
language:
C++14 (clang 8.0)
created:
1 hour ago
visibility:
secret

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!