P10258: 接触追踪2
传统题
1.000s
时间限制
128MB
内存限制
12 提交
5 解决
【题目描述】
【题目描述】
农夫约翰有N排成一行的奶牛(1≤N≤3·10^5)。不幸的是，有一种疾病正在蔓延。
最初，一些奶牛开始被感染。每天晚上，受感染的奶牛都会将疾病传播给左右两侧的奶牛(如果存在的话)。一旦奶牛被感染，它就会继续被感染。
经过几个晚上，农夫约翰意识到问题已经失控，所以他对奶牛进行了测试，以确定谁生病了。找出可能开始患病的奶牛的最小数量。
【输入格式】
第一行包含N ，农民约翰拥有的奶牛数量。
下一行包含一个N字符的位串，只有1和0，其中1示受
感染的奶牛，0代表经过一些夜晚后未感染的奶牛。
【输出格式】
输出一个整数：表示可能一
开始患病的奶牛的最小数量。
【样例输入1】
5
11111
【输出示例1】
1
【样例1说明】
假设中间的奶牛是唯一一头开始被感染的奶牛。然后奶牛会按照以下顺序被感染：
0晚：00100（第三头奶牛最初被感染）
1晚：->01110（第二头和第四头奶牛现在被感染）
2晚：->11111（第一头和第五头奶牛现在被感染）
3晚：->11111（所有奶牛都已被感染，因此没有其他奶牛被感染）
->。。。
在两个或多个晚上之后，奶牛的最终状态看起来就像输入。还有许多其他初始状态和夜晚数可能会产生输入状态，例如：
0晚：10001
1晚：->11011
2晚：->11111
或者：
0晚：01001
1晚：->11111
或者：
0晚：01000
1晚：->11100
2晚：->11110
3晚：->11111
所有这些初始状态都包含至少一头受感染的奶牛。
【样本输入2】
6
011101
【样本输出2】
4
唯一可能导致这种最终状态的初始状态和夜晚数是，如果没有夜晚过去，输入的四头受感染的奶牛中的每一头都开始生病。
【输入】
第一行包含N ，农民约翰拥有的奶牛数量。
下一行包含一个N字符的位串，只有1和0，其中1示受感染的奶牛，0代表经过一些夜晚后未感染的奶牛。
【输出】
输出一个整数：表示可能一开始患病的奶牛的最小数量。