ROCK  Sweet and Sour Rock
A manufacturer of sweets has started production of a new type of sweet called rock. Rock comes in sticks composed of onecentimetrelong 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.
Input
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).
Output
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.
Example
Sample input: 2 15 100110001010001 16 0010111101100000 Sample output: 9 13
hide comments
kalyanavuthu:
20180416 04:50:52
Last edit: 20180416 04:51:33 

sinersnvrsleep:
20180118 13:49:54
o(n3) solution is very easy plz give hint of o(n2) solution; 

ashishranjan28:
20170525 09:47:06
recursion partitioning + memoisation 

nilabja16180:
20170329 10:56:34
AC in one GO! 

cake_is_a_lie:
20170223 03:32:49
This problem can be solved in O(N) time, so for example on my computer I can solve instances with N=1000000 in <0.1s.


gautam:
20170222 12:11:33
nailed it :) 

iam_ss:
20170211 17:38:51
AC in first attempted. Very basic DP. 

flyingduchman_:
20161226 12:24:51
A modified Matrix Chain Multiplication algorithm (MCM) can solve it in O(n^3) using the dynamic programming(dp) approach. The idea is to generate all possible combination of subproblems and derive a formula that solves the problem in bottomup manner. Assuming you know the dp solution of MCM, let M[n][n] be a table where M[i,j] stores the solution of elements from i to j in given string. Generate all possible combination of arrayindex i, j, k i.e. i<=k<j. In the table each range(i to j) can have two properties like:


iharsh234:
20160803 16:28:51
1D DP + recursion faster then chain multiplication


Anuj Arora:
20160717 17:14:08
Phew ....Accepted....Missing condition to compare zeros and ones Last edit: 20160717 17:14:32 
Added by:  adrian 
Date:  20040803 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  based on a problem from the VII Polish Collegiate Team Programming Contest (AMPPZ), 2002 