题目描述
给你一个长度为 n 的 01 串 s,你可以进行操作:
选择一个操作集合 U⊆{0,1,⋯,n}(可以是空集) ,然后每次选择一个最大的 x∈U 并将其从 U 中删去,然后将 s[1,x] 按位取反,将 s[x+1,n] 翻转。 注意 s[1,x] 和 s[x+1,n] 都可以为空子串。
定义一个字符串 s 的价值为其满足相邻位不同的最长子段长度, 现在要求你选择一个操作集合,最大化操作完成后字符串 s 的价值,你只需要输出字符串的价值。
输入格式
给出一行 字符串s (只包含0/1)
输出格式
输出一行一个整数,表示答案
样例 #1
样例输入 #1
01111
样例输出 #1
3
样例 #2
样例输入 #2
10001
样例输出 #2
3
样例 #3
样例输入 #3
10001011101000001001
样例输出 #3
11
提示
定义n为输入数据的长度
Subtask 1 (10pts): n≤20
Subtask 2 (20pts): n≤300
Subtask 3 (20pts): n≤5000
Subtask 4 (50pts): 无特殊限制
对于 100% 的数据 n≤107
下面给出一种样例一最优解的构造:
选取集合U={1,4,5}
第一步 将[1,5]取反,[6,5]空区间不合法,序列变为[1,0,0,0,0]
第二步 将[1,4]取反,[5,5]翻转,序列变为[0,1,1,1,0]
第三步 将[1,1]取反,[2,5]翻转,序列变为[1,0,1,1,1]
可以发现[1,3]为符合题目要求的子段,答案为3。
可以证明,不存在更优的解