UOJ Logo

NOI.AC

1S 512MB
统计

题目描述

给你一个长度为 n 的 01 串 s,你可以进行操作:

选择一个操作集合 U{0,1,,n}() ,然后每次选择一个最大xU 并将其从 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): n20

Subtask 2 (20pts): n300

Subtask 3 (20pts): n5000

Subtask 4 (50pts): 无特殊限制

对于 100% 的数据 n107

下面给出一种样例一最优解的构造:

选取集合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。

可以证明,不存在更优的解