fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6.  
  7. #define EGRY                          \
  8.     ios_base::sync_with_stdio(false); \
  9.     cin.tie(NULL);
  10.  
  11. const int MAX = 100 + 50;
  12. const int MOD = 1e9 + 7;
  13.  
  14. int arr[MAX];
  15.  
  16. int num_of_evens(int n)
  17. {
  18.     return n / 2;
  19. }
  20.  
  21. int num_of_odds(int n)
  22. {
  23.     if (n % 2 == 0)
  24.     {
  25.         return n / 2;
  26.     }
  27.     else
  28.     {
  29.         return (n / 2) + 1;
  30.     }
  31. }
  32.  
  33. bool is_even(int n)
  34. {
  35.     return (n % 2 == 0);
  36. }
  37.  
  38. bool is_odd(int n)
  39. {
  40.     return !is_even(n);
  41. }
  42.  
  43. int mem[MAX][MAX][2];
  44.  
  45. int dp(int idx, int evens, int odds, bool last_is_odd, int n)
  46. {
  47.  
  48.     if (idx == n)
  49.     {
  50.         return 0;
  51.     }
  52.  
  53.     int &ret = mem[idx][evens][last_is_odd];
  54.  
  55.     if (ret != -1)
  56.     {
  57.         return ret;
  58.     }
  59.  
  60.     if (idx == 0)
  61.     {
  62.         if (arr[idx] != 0)
  63.         {
  64.             return ret = dp(idx + 1, evens, odds, arr[idx] % 2, n);
  65.         }
  66.         else
  67.         {
  68.             int pick_even = INT_MAX, pick_odd = INT_MAX;
  69.  
  70.             if (evens > 0)
  71.             {
  72.                 pick_even = dp(idx + 1, evens - 1, odds, false, n);
  73.             }
  74.  
  75.             if (odds > 0)
  76.             {
  77.                 pick_odd = dp(idx + 1, evens, odds - 1, true, n);
  78.             }
  79.  
  80.             return ret = min(pick_even, pick_odd);
  81.         }
  82.     }
  83.  
  84.     if (arr[idx] != 0)
  85.     {
  86.         bool cur_is_odd = arr[idx] % 2;
  87.         bool is_different = (cur_is_odd != last_is_odd);
  88.         return ret = is_different + dp(idx + 1, evens, odds, arr[idx] % 2, n);
  89.     }
  90.  
  91.     int pick_even = INT_MAX, pick_odd = INT_MAX;
  92.  
  93.     if (evens > 0)
  94.     {
  95.         bool cur_is_odd = false;
  96.         bool is_different = (cur_is_odd != last_is_odd);
  97.         pick_even = is_different + dp(idx + 1, evens - 1, odds, false, n);
  98.     }
  99.  
  100.     if (odds > 0)
  101.     {
  102.         bool cur_is_odd = true;
  103.         bool is_different = (cur_is_odd != last_is_odd);
  104.         pick_odd = is_different + dp(idx + 1, evens, odds - 1, true, n);
  105.     }
  106.  
  107.     return ret = min(pick_even, pick_odd);
  108. }
  109.  
  110. void solve()
  111. {
  112.     int n;
  113.     cin >> n;
  114.  
  115.     int evens = num_of_evens(n);
  116.     int odds = num_of_odds(n);
  117.  
  118.     for (int i = 0; i < n; i++)
  119.     {
  120.         cin >> arr[i];
  121.  
  122.         if (arr[i] == 0)
  123.         {
  124.             continue;
  125.         }
  126.  
  127.         if (is_even(arr[i]))
  128.         {
  129.             evens--;
  130.         }
  131.         else
  132.         {
  133.             odds--;
  134.         }
  135.     }
  136.  
  137.     memset(mem, -1, sizeof(mem));
  138.  
  139.     int space = evens + odds;
  140.  
  141.     cout << dp(0, evens, odds, false, n);
  142. }
  143.  
  144. int main()
  145. {
  146.     EGRY ll t = 1;
  147.     // cin >> t;
  148.  
  149.     while (t--)
  150.     {
  151.         solve();
  152.     }
  153.  
  154.     return 0;
  155. }
  156.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ue22ne
language:
C++14 (gcc 8.3)
created:
1 day 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!