← 返回题目列表

AtCoder · joig2021_c

C. 照明2

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

配点: 100 点

問題文

JOI高中的学生葵决定在学园祭期间用灯光装饰走廊。

照明是 沿东西方向创建一条N 灯泡线。灯泡从西侧依次排列。 它们的编号最大为 1 从 N 。每个灯泡都有一个开和关 2 有两种状态,最初所有灯泡都关闭。

葵的目标照明模式是一系列数字。 A_1, A_2, \ldots, A_N 灯泡时A_i = 1 打开 i , 我想在A_i = 0 时将其关闭。葵想在最短的时间内创造出这个图案。

Aoi 首先执行以下操作。 您只能执行此操作 1 次,但您不必这样做。

  • 从西端连续打开一段路段的灯泡。也就是说, 小于或等于 1 以上 N 的整数 r 它被转换为格式 1 选择一个,灯泡 打开 1, 2, \ldots , r 。

执行此操作所需的时间可以忽略不计。

之后,您可以多次执行以下操作。

  • 灯泡 1 选择一个并更改灯泡的状态(如果打开,则将其关闭,如果关闭,则将其打开)。

执行此操作 1 每次 需要 1 分钟。

给定灯泡数量和目标照明模式,编写一个程序来找出 Aoi 实现目标模式所需的最短分钟数。

制約

  • 1 \leqq N \leqq 200\,000.
  • A_i 是 仅由 0 或 1 (1 \leqq i \leqq N).
  • 所有输入值都是整数。

小課題

  1. (45 点) N \leqq 2\,000.
  2. (55 点)没有额外的限制。

评分注意事项

所有提交的内容都将通过评审系统进行评分。

当提交的源代码为与该子作业对应的所有评分输入数据返回正确的结果时,该源代码被认为对于该子作业是正确的。

每次提交的分数是所提交的源代码回答正确的子任务分数的总和。

该作业的分数是此作业的所有提交内容的最高分。

您可以在“提交结果”选项卡上的“我的分数状态”中查看您当前的分数。


入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N

出力

创建目标模式所需的最短分钟数将写入标准输出。 1 行。


入力例 1

6
0 1 1 0 0 1

出力例 1

2

比如葵先 选择 r = 3 和灯泡 打开 1, 2, 3 。这个操作所花费的时间是 现在是 0 分钟。然后是灯泡 1 从开到关,灯泡 将 6 的状态从关闭更改为打开。这些操作中的每一个 总共 1 分钟 2 分钟。2 由于不可能在不到几分钟的时间内实现所需的图案,2 。


入力例 2

4
0 0 0 1

出力例 2

1

在此输入示例中,Aoi 不执行第一个操作。然后是灯泡 4 的状态从关闭更改为打开。此操作需要 需要 1 分钟,1 由于不可能在不到几分钟的时间内实现所需的图案,1 。


入力例 3

4
1 1 1 1

出力例 3

0

在此输入示例中,Aoi 首先 r = 4 选择灯泡 通过打开 1, 2, 3, 4 ,您可以创建所需的图案。这个操作所花费的时间是 0 分钟,所以0 。


入力例 4

15
1 0 0 0 0 1 1 1 0 1 0 0 1 0 1

出力例 4

6