分数: 700 点
问题陈述
N 单元格排列成一行。
其中一些可能包含令牌。
给你一个字符串 s 包括 0和 1s。
如果 i第一个字符 s is 1, i第一个单元格(从左起)包含一个令牌。
否则,它不包含令牌。
Snuke 想要尽可能多次地执行以下操作。 在每次操作中,他选择三个连续的单元格。 我们称细胞为 X, Y, Z 从左到右。 为了使操作有效,两者 X 和 Z 必须包含令牌并且 Y 不得包含令牌。 然后,他删除这两个令牌并放置一个新令牌 Y.
如果他以最优方式执行操作,他可以执行多少次操作?
约束
- 1 \leq N \leq 500,000
- |s| = N
- 中的每个字符 s 是
0or1.
输入
输入由标准输入按以下格式给出:
N s
输出
打印答案。
示例输入 1
7 1010101
示例输出 1
2
例如,他可以通过以下方式执行两个操作:
- 对最后三个单元格执行操作。现在代表 token 的字符串变成了
1010010. - 对前三个单元格执行操作。现在代表 token 的字符串变成了
0100010.
请注意,操作的选择很重要。 例如,如果他先选择中间的三个单元格,则他不能再执行任何操作。
示例输入 2
50 10101000010011011110001001111110000101010111100110
示例输出 2
10