Cowntact Tracing 2

题目描述

农夫约翰有 $N$ 头奶牛排成一列（$1 \leq N \leq 3\cdot 10^5$）。不幸的是，一种疾病正在传播。 最初，有一些奶牛一开始就是感染的。每天晚上，一头感染的奶牛会把疾病传播给它左边和右边的奶牛（如果存在）。一旦一头奶牛被感染，她就会一直保持感染状态。 经过若干个夜晚后，农夫约翰意识到问题已经失控，于是他对奶牛进行检测以确定哪些奶牛患病。请找出一开始可能患病的奶牛的最小数量。

输入格式

第一行包含 $N$，表示农夫约翰拥有的奶牛数量。 第二行包含一个长度为 $N$ 的仅由 $1$ 和 $0$ 组成的二进制字符串，其中 $1$ 表示经过若干个夜晚后该奶牛感染，$0$ 表示经过若干个夜晚后该奶牛未感染。

输出格式

输出一个整数：一开始可能患病的奶牛的最小数量。

5
11111

1

6
011101

4

提示

假设中间那头奶牛是唯一一开始感染的奶牛。那么奶牛会按如下顺序被感染： 0 nights: 00100 (第三头奶牛最初被感染) 1 night: -> 01110 (第二和第四头奶牛现在被感染) 2 nights: -> 11111 (第一和第五头奶牛现在被感染) 3 nights: -> 11111 (所有奶牛之前就都已感染，因此没有额外奶牛被感染) -> ... 两晚或更多夜晚后，奶牛的最终状态将与输入相同。 还有许多其他的初始状态与夜晚数量也可能产生该输入状态，例如： 0 nights: 10001 1 night: -> 11011 2 nights: -> 11111 或： 0 nights: 01001 1 night: -> 11111 或： 0 nights: 01000 1 night: -> 11100 2 nights: -> 11110 3 nights: -> 11111 所有这些初始状态都至少包含一头感染的奶牛。

唯一能导致该最终状态的初始状态与夜晚数量是：没有夜晚经过，并且输入中那四头感染的奶牛各自一开始就患病。

评分： 测试点 3-7：$N \le 1000$ 测试点 8-12：无额外限制。 题目鸣谢：Suhas Nagar

标签: USACO|2023|Bronze

来源

USACO|2023|Bronze