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
#include <bits/stdc++.h>

using namespace std;

char x;
int z,n,a,b,p,l,bb,pp;
int t[100005];
int dp[100005][4];
vector <int> v;

int main()
{
    scanf("%d",&z);
    for (int zz=1; zz<=z; zz++)
    {
        scanf("%d",&n);
        for (int i=1; i<=n; i++)
        {
            scanf(" %c",&x);
            if (x=='0') t[i]=0;
            else t[i]=1;
        }
        p=1;
        a=0;
        b=0;
        while (t[p]!=1 && p<=n)
        {
            a++;
            p++;
        }
        if (a == n)
        {
            printf("0\n");
            continue;
        }
        p=n;
        while (t[p]!=1 && p>=1)
        {
            b++;
            p--;
        }
        bb=0;
        l=0;
        for (int i=1; i<=n; i++)
        {
            if (t[i]) 
            {
               if (bb) v.push_back(l);
               else bb=1;
               l=0;
            }
            else l++;
        }
        sort(v.begin(),v.end());
        reverse(v.begin(),v.end());
        dp[0][1]=b;
        dp[0][2]=a;
        dp[0][3]=a+b;
        if (a>0 && b>0) dp[0][3]--;
        p=0;
        pp=0;
        for (int i=0; i<v.size(); i++)
        {
            v[i]-=2*p;
            if (v[i]<=0) break;
            pp=i+1;
            if (v[i]>=3)
            {
                dp[i+1][0]=dp[i][0]+v[i]-1;
                p+=2;
                v[i]-=2;
                if (v[i]==1) v[i]++;
                dp[i+1][1]=max(dp[i][1]+v[i]-1,dp[i+1][0]+b-p);
                dp[i+1][2]=max(dp[i][2]+v[i]-1,dp[i+1][0]+a-p);
                v[i]-=2;
                if (v[i]==1) v[i]++;
                dp[i+1][3]=max(dp[i][3]+v[i]-1,max(dp[i+1][1]+a-p-1,dp[i+1][2]+b-p-1));
                dp[i+1][3]=max(dp[i+1][3],dp[i+1][0]+a-p+b-p-1);
            }
            else
            {
                dp[i+1][0]=dp[i][0]+1;
                p++;
                dp[i+1][1]=max(dp[i][1],dp[i+1][0]+b-p);
                dp[i+1][2]=max(dp[i][2],dp[i+1][0]+a-p);
                dp[i+1][3]=max(dp[i][3],max(dp[i+1][1]+a-p-1,dp[i+1][2]+b-p-1));
                dp[i+1][3]=max(dp[i+1][3],dp[i+1][0]+a-p+b-p-1);
            }
            dp[i+1][0]=max(dp[i+1][0],dp[i][0]);
            dp[i+1][1]=max(dp[i+1][1],dp[i][1]);
            dp[i+1][2]=max(dp[i+1][2],dp[i][2]);
            dp[i+1][3]=max(dp[i+1][3],dp[i][3]);
        }
        printf("%d\n",n-max(max(dp[pp][0],dp[pp][1]),max(dp[pp][2],dp[pp][3])));
        v.clear();
    }
}