← 返回题目列表

AtCoder · awc0046_c

C. 座位安排

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

分数: 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