问题 C: 3.佛珠 (Beads)

问题 C: 3.佛珠 (Beads)

题目描述

  获得密码后,乔普很容易得打开宝藏的大门,首先看到的是一串长长的佛珠,这串佛珠只有两种颜色:黑色和白色。普雷斯的法力能将连续相同颜色的佛珠,变成另一种颜色,作为有强迫症的乔普,想把它变成一种颜色,可是普雷斯的法力有限,他只能使用n次魔法,所以不一定能使所有的佛珠变成同一种颜色,尽可能获得最长的同一种颜色的佛珠。你知道普雷斯使用n次魔法后,佛珠上同一种颜色珠子的最长长度是多少吗?

输入

共两行,第一行一个整数n,表示普雷斯使用的魔法次数;
第二行,由01组成一字符串,表示原佛珠的状态,0表示白色,1表示黑色。

输出

一个整数,表示经普雷斯施放n次魔法后,佛珠上同一种颜色珠子的最长长度。

样例输入输出

输入#1 复制
2
0011100000111111111000111111000000000 
输出#1 复制
32
输入#2 复制
3
0010010010011101010
输出#2 复制
12

提示

【样例说明】
样例1:
原佛珠:        0011100000111111111000111111000000000
第一施法后: 0011100000111111111000000000000000000
第二施法后: 0011100000000000000000000000000000000
样例2:
原佛珠:        0010010010011101010
第一施法后: 0010010010000001010 
第二施法后: 0010010000011101010
第三施法后: 0010000000000001010
【数据范围约定】
30%   1≤n≤2,字符串长度小于100,黑白段数小于10;
60%   1≤n≤100,字符串长度小于100000,黑白段数小于1000;
100%  1≤n≤10000,字符串长度小于10000000,黑白段数小于100000。
【说明】
魔法施放到一半时,整串佛珠已经是一种颜色,就不需要再施加魔法了。


序号 标题 作者 发表时间 费用 订购数 操作