#2078. [USACO23DEC] Cowntact Tracing 2 B

[USACO23DEC] Cowntact Tracing 2 B

题目描述

Farmer John 有 NN 头奶牛排成一列(1N31051 \leq N \leq 3\cdot 10^5)。不幸的是,有一种疾病正在传播。

最初,有一些奶牛被感染。每到夜晚,被感染的奶牛会将疾病传播给它左右两边的奶牛(如果这些奶牛存在的话)。一旦奶牛被感染,她就会持续处于感染状态。

经过一些晚上,Farmer John 意识到情况已经失控,因此他对奶牛进行了检测以确定哪些奶牛感染了疾病。请找出最少有多少头奶牛最初可能感染了这种疾病。

输入格式

第一行为一个整数 NN,即 Farmer John 拥有的奶牛数量。

接下来一行,包含长度为 NN 的由 1100 组成的位串。其中 11 表示一头被感染的奶牛,00 表示一头在经过若干晚之后仍未被感染的奶牛。

输出格式

输出一个整数,表示最少有多少头奶牛可能最初感染了这种疾病。

样例 #1

样例输入 #1

5
11111

样例输出 #1

1

样例 #2

样例输入 #2

6
011101

样例输出 #2

4

提示

样例解释 1

假设只有中间的奶牛最初被感染。那么,奶牛们将按以下顺序被感染:

  • 00 晚:0010000100(第三只奶牛一开始被感染)
  • 11 晚:0111001110(第二和第四只奶牛现在被感染了)
  • 22 晚:1111111111(第一和第五只奶牛现在被感染了)
  • 33 晚:1111111111(所有的奶牛都已经被感染了,没有新的奶牛被感染)
  • ……

经过两个或更多的晚上,奶牛们的状态即与输入的状态相符。还有许多其他的初始状态和夜晚数量可能导致了输入的状态,例如:

  • 00 晚:1000110001
  • 11 晚:1101111011
  • 22 晚:1111111111

或者:

  • 00 晚:0100101001
  • 11 晚:1111111111

或者:

  • 00 晚:0100001000
  • 11 晚:1110011100
  • 22 晚:1111011110
  • 33 晚:1111111111

所有这些初始状态中至少有一头奶牛被感染。

样例解释 2

唯一可能导致这个最终状态的初始状态和夜晚数是:没有经过任何夜晚,输入中的四头感染的奶牛都是从最开始就感染了这种疾病。

测试点性质

  • 测试点 373-7 满足 N1000N \le 1000
  • 测试点 8128-12 没有额外限制。