Garland
1 #include <cstdio>
2 #include <iostream>
3 #include <cstdio>
4 #include <algorithm>
5 #include <functional>
6 #include <set>
7 #include <vector>
8 #include <queue>
9 #include <cstring>
10 #include <stack>
11 #include <climits>
12
13 using namespace std;
14
15 #define ll long long
16 #define pb push_back
17 #define fi first
18 #define se second
19
20 //dp[i][j][0/1] 表示前i位数字中有j位偶数，且当前是偶/奇数
21
22 void solve(){
23
24 // int T;
25 // cin >> T;
26 // while(T--){
27 int n;
28 cin >> n;
29 vector<int > a(n);
30 for(auto& x : a) cin >> x;
31 vector<vector<vector<int > > > dp(n + 1, vector<vector<int> >(n + 1, vector<int >(2, 1e9)));
32 dp[0][0][0] = dp[0][0][1] = 0;
33 for(int i = 1; i <= n; ++i){
34 for(int j = 0; j <= i; ++j){
35 if(a[i - 1] % 2 == 1 || a[i - 1] == 0){
36 dp[i][j][1] = min(dp[i - 1][j][0] + 1, dp[i - 1][j][1]);
37 }
38 if(a[i - 1] % 2 == 0 && j > 0){
39 dp[i][j][0] = min(dp[i - 1][j - 1][1] + 1, dp[i - 1][j - 1][0]);
40 }
41 }
42 }
43 cout << max(dp[n][n ][1], dp[n][n][0]) << endl;
44 // cout << dp[n][n][1] << endl;
45 // cout << dp[n][n][0] << endl;
46
47 // }
48 }
49
50 int main(){
51
52 // freopen("C:\Users\admin\Desktop\input.txt", "r", stdin);
53 // freopen("C:\Users\admin\Desktop\output.txt", "w", stdout);
54 ios::sync_with_stdio(false);
55 cin.tie(0);
56 cout.tie(0);
57 solve();
58
59 return 0;
60 }