#include <bits/stdc++.h> #define rep(i, a, b) for (int i = a; i <= b; i++) #define per(i, a, b) for (int i = b; a <= i; i--) #define cat(x) cerr << #x << " = " << x << '\n'; using ll = long long; using namespace std; const int N = 111000; int n, dp[N][3]; string s; vector<int> v; void solve() { cin >> n >> s; v.clear(); int last = -1; rep(i, 0, n - 1) { if (s[i] == '1') { if (last >= 0) { v.push_back(i - last - 1); } last = i; } } if (last == -1) { cout << 0 << '\n'; return; } sort(v.rbegin(), v.rend()); int w[2]{}; for (int i = 0; s[i] == '0'; w[0]++, i++); for (int i = n - 1; s[i] == '0'; w[1]++, i--); if (w[0] < w[1]) swap(w[0], w[1]); int m = int(v.size()); rep(i, 0, m) rep(j, 0, 2) dp[i][j] = 0; auto upd = [&](int &a, int b) { a = max(a, b); }; auto f1 = [&](int x, int tim) { return max(0, x - tim); }; auto f2 = [&](int x, int tim) { x -= 2 * tim; if (x <= 0) return 0; if (x == 1) return 1; return x - 1; }; // bigger segments go before smallers rep(i, 0, m) { // outside segments upd(dp[i][1], dp[i][0] + f1(w[0], 2 * i)); upd(dp[i][2], dp[i][1] + f1(w[1], 2 * i + 1)); // inside segment if (i < m) { rep(j, 0, 2) { upd(dp[i + 1][j], dp[i][j] + f2(v[i], 2 * i + j)); } } } cout << n - dp[m][2] << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int t; cin >> t; while (t--) { solve(); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #include <bits/stdc++.h> #define rep(i, a, b) for (int i = a; i <= b; i++) #define per(i, a, b) for (int i = b; a <= i; i--) #define cat(x) cerr << #x << " = " << x << '\n'; using ll = long long; using namespace std; const int N = 111000; int n, dp[N][3]; string s; vector<int> v; void solve() { cin >> n >> s; v.clear(); int last = -1; rep(i, 0, n - 1) { if (s[i] == '1') { if (last >= 0) { v.push_back(i - last - 1); } last = i; } } if (last == -1) { cout << 0 << '\n'; return; } sort(v.rbegin(), v.rend()); int w[2]{}; for (int i = 0; s[i] == '0'; w[0]++, i++); for (int i = n - 1; s[i] == '0'; w[1]++, i--); if (w[0] < w[1]) swap(w[0], w[1]); int m = int(v.size()); rep(i, 0, m) rep(j, 0, 2) dp[i][j] = 0; auto upd = [&](int &a, int b) { a = max(a, b); }; auto f1 = [&](int x, int tim) { return max(0, x - tim); }; auto f2 = [&](int x, int tim) { x -= 2 * tim; if (x <= 0) return 0; if (x == 1) return 1; return x - 1; }; // bigger segments go before smallers rep(i, 0, m) { // outside segments upd(dp[i][1], dp[i][0] + f1(w[0], 2 * i)); upd(dp[i][2], dp[i][1] + f1(w[1], 2 * i + 1)); // inside segment if (i < m) { rep(j, 0, 2) { upd(dp[i + 1][j], dp[i][j] + f2(v[i], 2 * i + j)); } } } cout << n - dp[m][2] << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int t; cin >> t; while (t--) { solve(); } return 0; } |