#include <bits/stdc++.h> using namespace std; int solveRec(int iOnes, int iTwos, int timeSoFar, vector <int> &indOnes, vector <int> &indTwos, const vector <pair<int,int>> &gaps) { int nOnes = indOnes.size(), nTwos = indTwos.size(); if (iOnes < nOnes && gaps[indOnes[iOnes]].first <= timeSoFar) iOnes = nOnes; if (iTwos < nTwos && gaps[indTwos[iTwos]].first <= 2 * timeSoFar) iTwos = nTwos; if (iOnes == nOnes && iTwos == nTwos) { return 0; } bool tryOne, tryTwo; if (iOnes == nOnes) { tryOne = false, tryTwo = true; } else if (iTwos == nTwos) { tryOne = true, tryTwo = false; } else { int gainOne = gaps[indOnes[iOnes]].first - timeSoFar; int valueTwo = gaps[indTwos[iTwos]].first - 2 * timeSoFar; int gainTwo = valueTwo - (valueTwo >= 2); tryOne = gainOne >= gainTwo || gainOne <= 3; tryTwo = gainTwo > gainOne; } int ans = 0; if (tryOne) { int fst = gaps[indOnes[iOnes]].first - timeSoFar; ans = max( ans, fst + solveRec(iOnes + 1, iTwos, timeSoFar + 1, indOnes, indTwos, gaps) ); } if (tryTwo) { int fst = gaps[indTwos[iTwos]].first - 2 * timeSoFar; ans = max( ans, fst - (fst >= 2) + solveRec(iOnes, iTwos + 1, timeSoFar + (fst >= 3 ? 2 : 1), indOnes, indTwos, gaps) ); } return ans; } int solveGaps(vector <pair<int,int>> &gaps) { vector <int> indOnes, indTwos; for (int i = 0; i < (int) gaps.size(); i++) { if (gaps[i].second == 1) { indOnes.push_back(i); } else { indTwos.push_back(i); } } sort(indOnes.begin(), indOnes.end(), [&](int i, int j) { return gaps[i].first > gaps[j].first; }); sort(indTwos.begin(), indTwos.end(), [&](int i, int j) { return gaps[i].first > gaps[j].first; }); int timeSoFar = 0; return solveRec(0, 0, timeSoFar, indOnes, indTwos, gaps); } int solve(int n, const string &s) { vector <pair<int,int>> gaps; for (int l = 0; l < n; l++) if (s[l] == '0') { int r = l; while (r < n - 1 && s[r + 1] == '0') { r++; } if (l == 0 && r == n - 1) { return 0; } else { gaps.push_back({r - l + 1, (l != 0) + (r != n - 1)}); } l = r; } if (gaps.empty()) { return n; } return n - solveGaps(gaps); } int main() { ios_base::sync_with_stdio(false); int t; cin >> t; while (t--) { int n; cin >> n; string s; cin >> s; cout << solve(n, s) << '\n'; } 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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | #include <bits/stdc++.h> using namespace std; int solveRec(int iOnes, int iTwos, int timeSoFar, vector <int> &indOnes, vector <int> &indTwos, const vector <pair<int,int>> &gaps) { int nOnes = indOnes.size(), nTwos = indTwos.size(); if (iOnes < nOnes && gaps[indOnes[iOnes]].first <= timeSoFar) iOnes = nOnes; if (iTwos < nTwos && gaps[indTwos[iTwos]].first <= 2 * timeSoFar) iTwos = nTwos; if (iOnes == nOnes && iTwos == nTwos) { return 0; } bool tryOne, tryTwo; if (iOnes == nOnes) { tryOne = false, tryTwo = true; } else if (iTwos == nTwos) { tryOne = true, tryTwo = false; } else { int gainOne = gaps[indOnes[iOnes]].first - timeSoFar; int valueTwo = gaps[indTwos[iTwos]].first - 2 * timeSoFar; int gainTwo = valueTwo - (valueTwo >= 2); tryOne = gainOne >= gainTwo || gainOne <= 3; tryTwo = gainTwo > gainOne; } int ans = 0; if (tryOne) { int fst = gaps[indOnes[iOnes]].first - timeSoFar; ans = max( ans, fst + solveRec(iOnes + 1, iTwos, timeSoFar + 1, indOnes, indTwos, gaps) ); } if (tryTwo) { int fst = gaps[indTwos[iTwos]].first - 2 * timeSoFar; ans = max( ans, fst - (fst >= 2) + solveRec(iOnes, iTwos + 1, timeSoFar + (fst >= 3 ? 2 : 1), indOnes, indTwos, gaps) ); } return ans; } int solveGaps(vector <pair<int,int>> &gaps) { vector <int> indOnes, indTwos; for (int i = 0; i < (int) gaps.size(); i++) { if (gaps[i].second == 1) { indOnes.push_back(i); } else { indTwos.push_back(i); } } sort(indOnes.begin(), indOnes.end(), [&](int i, int j) { return gaps[i].first > gaps[j].first; }); sort(indTwos.begin(), indTwos.end(), [&](int i, int j) { return gaps[i].first > gaps[j].first; }); int timeSoFar = 0; return solveRec(0, 0, timeSoFar, indOnes, indTwos, gaps); } int solve(int n, const string &s) { vector <pair<int,int>> gaps; for (int l = 0; l < n; l++) if (s[l] == '0') { int r = l; while (r < n - 1 && s[r + 1] == '0') { r++; } if (l == 0 && r == n - 1) { return 0; } else { gaps.push_back({r - l + 1, (l != 0) + (r != n - 1)}); } l = r; } if (gaps.empty()) { return n; } return n - solveGaps(gaps); } int main() { ios_base::sync_with_stdio(false); int t; cin >> t; while (t--) { int n; cin >> n; string s; cin >> s; cout << solve(n, s) << '\n'; } return 0; } |