← 返回题目列表

AtCoder · code_festival_2017_qualb_d

D. 101 至 010

中文机器翻译题面 查看原题

分数: 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 是 0 or 1.

输入

输入由标准输入按以下格式给出:

N
s

输出

打印答案。


示例输入 1

7
1010101

示例输出 1

2

例如,他可以通过以下方式执行两个操作:

  • 对最后三个单元格执行操作。现在代表 token 的字符串变成了 1010010.
  • 对前三个单元格执行操作。现在代表 token 的字符串变成了 0100010.

请注意,操作的选择很重要。 例如,如果他先选择中间的三个单元格,则他不能再执行任何操作。


示例输入 2

50
10101000010011011110001001111110000101010111100110

示例输出 2

10