思路：
可以使用动态规划。
实现：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int INF = 0x3f3f3f3f; 4 int a[105], dp[105][105][105][2], n; 5 int dfs(int cur, int o, int e, int last) 6 { 7 if (cur == n) return 0; 8 if (dp[cur][o][e][last] != -1) return dp[cur][o][e][last]; 9 int res = INF; 10 if (a[cur] == 0) 11 { 12 if (o) res = min(res, dfs(cur + 1, o - 1, e, 1) + (last != 1)); 13 if (e) res = min(res, dfs(cur + 1, o, e - 1, 0) + (last != 0)); 14 } 15 else 16 { 17 res = dfs(cur + 1, o, e, a[cur] & 1) + ((a[cur] & 1) != last); 18 } 19 return dp[cur][o][e][last] = res; 20 } 21 int main() 22 { 23 while (cin >> n) 24 { 25 memset(dp, -1, sizeof dp); 26 int o = n / 2, e = n / 2; 27 if (n & 1) o++; 28 int oo = 0, ee = 0; 29 for (int i = 0; i < n; i++) 30 { 31 cin >> a[i]; 32 if (!a[i]) continue; 33 if (a[i] & 1) oo++; 34 else ee++; 35 } 36 if (n == 1) { cout << 0 << endl; continue; } 37 o -= oo; e -= ee; 38 int res = INF; 39 if (a[0] == 0) res = min(dfs(1, o - 1, e, 1), dfs(1, o, e - 1, 0)); 40 else res = dfs(1, o, e, a[0] & 1); 41 cout << res << endl; 42 } 43 return 0; 44 }