A manufacturer of sweets has started production of a new type of sweet called rock. Rock comes in sticks composed of one-centimetre-long segments, some of which are sweet, and the rest are sour. Before sale, the rock is broken up into smaller pieces by splitting it at the connections of some segments.

Today‘s children are very particular about what they eat, and they will only buy a piece of rock if it contains more sweet segments than sour ones. Try to determine the total length of rock which can be sold after breaking up the rock in the best possible way.

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case, the first line of input contains one integer N - the length of the stick in centimetres (1<=N<=200). The next line is a sequence of N characters ‘0‘ or ‘1‘, describing the segments of the stick from the left end to the right end (‘0‘ denotes a sour segment, ‘1‘ - a sweet one).

For each test case output a line with a single integer: the total length of rock that can be sold after breaking up the rock in the best possible way.

Sample input:215100110001010001160010111101100000Sample output:913

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int maxn = 205; 6 char str[maxn]; 7 int dp[maxn],sum[maxn][2]; 8  9 int main(){10     int T,len;11     scanf("%d",&T);12     while(T--){13         scanf("%d %s",&len,str+1);14         sum[0][0] = sum[0][1] = 0;15         for(int i = 1;i <= len;i++){16             sum[i][0] = sum[i-1][0];17             sum[i][1] = sum[i-1][1];18             sum[i][str[i]-‘0‘]++;//记录‘0’，‘1’出线的次数19         }20         dp[0] = 0;21         for(int i = 1;i <= len;i++){22             dp[i] = dp[i-1];23             for(int j = 1;j <= i;j++){24                 int sum0 = sum[i][0]-sum[j-1][0];25                 int sum1 = sum[i][1]-sum[j-1][1];26                 if(sum1 <= sum0)    continue;//‘0‘比‘1’多的时候27                 dp[i] = max(dp[i],dp[j-1]+i-j+1);//状态转移方程28             }29         }30         printf("%d\n",dp[len]);31     }32     return 0;33 }