fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define loi long long
  4.  
  5. //Failing at -> 1 0 0 13 0 0 16 0 0 4 0 0 7 0 19 0 0 10 0 0
  6.  
  7. pair<loi, loi> dp[100][100][100];
  8. //    min, parity
  9. pair<loi, loi> garland(loi ar[], loi n, loi evecnt, loi oddcnt, loi idx)
  10. {
  11.   //  cout << "idx = : " << idx << " evecnt : " << evecnt << " oddcnt : " << oddcnt << "\n";
  12.  
  13.     if(dp[idx][evecnt][oddcnt].first != INT_MAX)
  14.        return dp[idx][evecnt][oddcnt];
  15.  
  16.     if(ar[idx] != 0)
  17.     {
  18.         if(idx == n - 1)
  19.         {
  20.             return (dp[idx][evecnt][oddcnt] = make_pair(0, ar[idx] & 1));
  21.         }
  22.  
  23.         else
  24.         {
  25.             pair<loi, loi> p1 = garland(ar, n, evecnt, oddcnt, idx + 1);
  26.             dp[idx][evecnt][oddcnt].first = p1.first + (((ar[idx] & 1) == p1.second) ? 0 : 1);
  27.             dp[idx][evecnt][oddcnt].second = ar[idx] & 1;
  28.  
  29.             return dp[idx][evecnt][oddcnt];
  30.         }
  31.     }
  32.  
  33.     else
  34.     {
  35.        if(idx == n - 1)
  36.        {
  37.            if(evecnt > 0)
  38.               return(dp[idx][evecnt][oddcnt] = make_pair(0, 0));
  39.  
  40.            else if(oddcnt > 0)
  41.               return(dp[idx][evecnt][oddcnt] = make_pair(0, 1));
  42.        }
  43.  
  44.        else
  45.        {
  46.            if(evecnt > 0)
  47.            {
  48.                pair<loi, loi> p2 = garland(ar, n, evecnt - 1, oddcnt, idx + 1);
  49.                dp[idx][evecnt][oddcnt] = make_pair((p2.first + ((p2.second == 0) ? 0 : 1)), 0);
  50.            }
  51.  
  52.            if(oddcnt > 0)
  53.            {
  54.                pair<loi, loi> p3 = garland(ar, n, evecnt, oddcnt - 1, idx + 1);
  55.                p3.first += ((p3.second == 1) ? 0 : 1);
  56.                p3.second = 1;
  57.  
  58.                if(dp[idx][evecnt][oddcnt].first > p3.first)
  59.                   dp[idx][evecnt][oddcnt] = p3;
  60.            }
  61.  
  62.            return dp[idx][evecnt][oddcnt];
  63.        }
  64.     }
  65. }
  66.  
  67. int main()
  68. {
  69.     loi n;
  70.  
  71.     cin >> n;
  72.  
  73.     loi ar[n], freq[n + 1];
  74.  
  75.     memset(freq, 0, sizeof(freq));
  76.  
  77.     for(loi i = 0; i < n; i++)
  78.     {
  79.         cin >> ar[i];
  80.  
  81.         if(ar[i])
  82.             freq[ar[i]]++;
  83.     }
  84.  
  85.     loi evecnt = 0, oddcnt = 0;
  86.  
  87.     for(loi i = 1; i <= n; i++)
  88.     {
  89.         if(!freq[i]){
  90.             if(i & 1)
  91.               oddcnt++;
  92.  
  93.             else evecnt++;}
  94.     }
  95.  
  96.     //cout << "Even count hai : " << evecnt << "  Odd count hai : " << oddcnt << "\n";
  97.  
  98.     for(loi i = 0; i < 100; i++)
  99.         for(loi j = 0; j < 100; j++)
  100.            for(loi k = 0; k < 100; k++)
  101.               dp[i][j][k] = make_pair(INT_MAX, 5);
  102.  
  103.     loi ans = (garland(ar, n, evecnt, oddcnt, 0)).first;
  104.  
  105.  
  106.     /*cout << "DP array bani hai -> \n";
  107.  
  108.     for(loi i = 0; i < 100; i++)
  109.         for(loi j = 0; j < 100; j++)
  110.           for(loi k = 0; k < 100; k++)
  111.              if(dp[i][j][k].first != INT_MAX)
  112.                 cout << "idx : " << i << " evecnt : " << evecnt << " oddcnt : " << oddcnt << "  " << dp[i][j][k].first << "\n";
  113.     */
  114.     cout << ans << "\n";
  115.  
  116.     return 0;
  117. }
  118.  
Success #stdin #stdout 0s 19040KB
comments (?)
stdin
copy 
5
0 5 0 2 3
stdout
copy 
2
https://ideone.com/XD6cll
language:
C++14 (gcc 8.3)
created:
4 years 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!