/* -*- coding: utf-8 -*- * * 1606.cc: No.1606 Stuffed Animals Keeper - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 5000; const int INF = 1 << 30; /* typedef */ /* global variables */ int as[MAX_N], cs[2], ls[MAX_N], lcs[MAX_N][2]; int dp[MAX_N + 1][MAX_N + 1]; /* subroutines */ inline void setmin(int &a, int b) { if (a > b) a = b; } /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", as + i); int m = 0; for (int i = 0; i < n;) { while (i < n && as[i] == 2) i++; if (i >= n) break; int j = i; while (j < n && as[j] != 2) { cs[as[j]]++; lcs[m][as[j]]++; j++; } ls[m] = j - i; m++; i = j; } //for (int i = 0; i < m; i++) //printf("%d(%d,%d) ", ls[i], lcs[i][0], lcs[i][1]); putchar('\n'); for (int i = 0; i <= m; i++) fill(dp[i], dp[i] + cs[0] + 1, INF); dp[0][0] = 0; for (int i = 0; i < m; i++) for (int j = 0; j <= cs[0]; j++) if (dp[i][j] < INF) { // -> 0 if (j + ls[i] <= cs[0]) setmin(dp[i + 1][j + ls[i]], dp[i][j] + lcs[i][1]); // -> 1 setmin(dp[i + 1][j], dp[i][j] + lcs[i][0]); } printf("%d\n", (dp[m][cs[0]] < INF) ? dp[m][cs[0]] / 2 : -1); return 0; }