fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. #define all(v)        ((v).begin()), ((v).end())
  6. #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
  7. #define pb            push_back
  8. #define ppb           pop_back
  9. #define F             first
  10. #define S             second
  11. #define B             begin()
  12. #define E             end()
  13. #define clr(x)        memset(x,0,sizeof(x))
  14. #define endl          '\n'
  15. #define coutfloat(n,d)     cout << fixed << setprecision(d) << n << endl
  16. #define FASTIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  17.  
  18. // #define int long long
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef long double   ld;
  22. typedef pair<int, int> pi;
  23. typedef vector<bool>      vb;
  24. typedef vector<vb>        vvb;
  25. typedef vector<string>    vs;
  26. typedef vector<int>       vi;
  27. typedef vector<ll>       vll;
  28. typedef vector<double>    vd;
  29. typedef vector< vi >      vvi;
  30.  
  31.  
  32. #ifndef ONLINE_JUDGE
  33. #define deb(x) cerr << #x <<" "; _print(x); cerr << endl;
  34. #else
  35. #define deb(x)
  36. #endif
  37.  
  38. void _print(ll t) {cerr << t;}
  39. void _print(int t) {cerr << t;}
  40. void _print(string t) {cerr << t;}
  41. void _print(char t) {cerr << t;}
  42. void _print(ld t) {cerr << t;}
  43. void _print(double t) {cerr << t;}
  44. void _print(ull t) {cerr << t;}
  45.  
  46. template <class T, class V> void _print(pair <T, V> p);
  47. template <class T> void _print(vector <T> v);
  48. template <class T> void _print(set <T> v);
  49. template <class T, class V> void _print(map <T, V> v);
  50. template <class T> void _print(multiset <T> v);
  51. template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}";}
  52. template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  53. template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  54. template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  55. template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  56.  
  57. const int dx[] = {0,0,1,-1};
  58. const int dy[] = {1,-1,0,0};
  59.  
  60. const ll inf = 1e9+1000;
  61. const double eps = (1e-8);
  62. const ll mod = 1e9 + 7;
  63.  
  64. const int N = 2e5+1000, M = 10;
  65. int k,n,m;
  66. vi a;
  67. ll dp[N][2]={};
  68. ll getMin(int ind, int del){
  69.     if(ind>=n) return 0;
  70.     if(dp[ind][del]!=-1) return dp[ind][del];
  71.     ll ans = inf;
  72.     deb(ind) deb(del)
  73.     if(a[ind] - 2*del<=0){
  74.         return dp[ind][del]= min(getMin(ind+1, 0), getMin(ind+1, 1) + 1);
  75.     }
  76.     else{
  77.         ans = getMin(ind+1, 0);
  78.         if(a[ind] -2* del <= 2){
  79.             ans = min(ans, getMin(ind+1, 1));
  80.         }
  81.         return dp[ind][del] = ans+1;
  82.     }
  83.  
  84. }
  85. void solve(){
  86.     cin>>n;
  87.     rep(i,0,2){
  88.         rep(j,0,n+10){
  89.             dp[j][i]=-1;
  90.         }
  91.     }
  92.     a = vi(n);
  93.     rep(i,0,n) cin>>a[i];
  94.     cout<<getMin(0,0)<<endl;;
  95.     // deb("n")
  96. }
  97. // #undef int;
  98. int main(){
  99.     FASTIO;
  100.  
  101.     int t= 1;
  102.     cin>>t;
  103.     while(t--) solve();
  104.  
  105. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
10
1
0
4
2 4 4 2
4
3 2 1 0
3
0 3 0
3
0 1 3
3
3 1 0
4
3 1 0 3
4
0 2 2 2
6
1 3 4 2 0 4
8
2 2 5 2 3 4 2 4
stdout
copy 
0
3
2
1
2
2
3
2
4
6
https://ideone.com/z4oLGz
language:
C++ (gcc 8.3)
created:
49 days 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!