分数: 366 分
问题陈述
高桥负责整理 N 文化节会场座位排成一排。座位有编号 1 通过 N 从左到右。
目前,部分座位已被客人占用。具体来说,座位 i 被占用,如果 S_i = 1,如果 S_i = 0.
高桥可以选择 0 或更多他喜欢的空座位,并引导一位新客人到每个选定的座位。但是,他不能移动或带走已经入座的客人。另外,每个座位最多可容纳 1 人。此外,根据场地通风规则,必须满足以下条件:
- 所有客人都被引导到座位后,必须有 没有连续三个座位全部被占用.
换句话说,如果我们表示座椅的状态 i 所有指导完成后 T_i (1 如果被占用, 0 如果空),那么对于每个 i 满意 1 \leq i \leq N-2,一定不能是这样的情况 T_i = T_{i+1} = T_{i+2} = 1。在输入中保证初始状态已经满足这个条件。
高桥希望在满足此条件的同时引导尽可能多的新客人。找出可以引导的新客人的最大数量。
约束
- 1 \leq N \leq 2 \times 10^5
- S_i \in \{0, 1\} (1 \leq i \leq N)
- 在输入中给出的初始状态下,不存在全部被占用的三个连续座位。也就是说,没有 i (1 \leq i \leq N-2)这样 S_i = S_{i+1} = S_{i+2} = 1.
- 所有输入值均为整数。
输入
N S_1 S_2 \ldots S_N
- 第一行包含一个整数 N 代表席位数。
- 第二行包含 N 整数 S_1, S_2, \ldots, S_N 以空格分隔,代表每个座位是否被占用。 S_i = 1 表示座位 i 被占用,并且 S_i = 0 表示它是空的。
输出
一行打印满足条件时可引导的最大新客人数量。
示例输入 1
5 0 0 1 0 0
示例输出 1
2
示例输入 2
7 1 0 0 0 0 0 1
示例输出 2
3
示例输入 3
15 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0
示例输出 3
7
示例输入 4
30 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0
示例输出 4
12
示例输入 5
1 0
示例输出 5
1