1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int n, a[110], f[110][110][110][2]; bool vis[110][110][110][2]; // 前p个数,第p个数,还剩c0个偶数,c1个奇数,取a[p]=x(x==0偶数,x==1奇数) int dfs(int p, int c0, int c1, int x) { if (a[p] && a[p]%2 != x) return -1; if (c0 < 0 || c1 < 0) return -1; if (!p) return 0; if (vis[p][c0][c1][x]) return f[p][c0][c1][x]; vis[p][c0][c1][x] = true; int &u = f[p][c0][c1][x]; for (int i = 0; i < 2; i++) { int tmp = dfs(p-1, c0 - (x%2==0), c1 - (x%2==1), i); if (tmp == -1) continue; int d = (p > 1) && (i != x); if (u == -1 || u > tmp + d) u = tmp + d; } return u; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", a+i); } memset(f, -1, sizeof f); int ans = -1; for (int i = 0; i < 2; i++) { int tmp = dfs(n, n/2, (n+1)/2, i); if (tmp != -1) if (ans == -1 || ans > tmp) ans = tmp; } printf("%d\n", ans); return 0; }
- 1
信息
- ID
- 13
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- (无)
- 递交数
- 0
- 已通过
- 0
- 上传者