310544: CF1849D. Array Painting

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

D. Array Paintingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given an array of $n$ integers, where each integer is either $0$, $1$, or $2$. Initially, each element of the array is blue.

Your goal is to paint each element of the array red. In order to do so, you can perform operations of two types:

  • pay one coin to choose a blue element and paint it red;
  • choose a red element which is not equal to $0$ and a blue element adjacent to it, decrease the chosen red element by $1$, and paint the chosen blue element red.

What is the minimum number of coins you have to spend to achieve your goal?

Input

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 2$).

Output

Print one integer — the minimum number of coins you have to spend in order to paint all elements red.

ExamplesInput
3
0 2 0
Output
1
Input
4
0 0 1 1
Output
2
Input
7
0 1 0 0 1 0 2
Output
4
Note

In the first example, you can paint all elements red with having to spend only one coin as follows:

  1. paint the $2$-nd element red by spending one coin;
  2. decrease the $2$-nd element by $1$ and paint the $1$-st element red;
  3. decrease the $2$-nd element by $1$ and paint the $3$-rd element red.

In the second example, you can paint all elements red spending only two coins as follows:

  1. paint the $4$-th element red by spending one coin;
  2. decrease the $4$-th element by $1$ and paint the $3$-rd element red;
  3. paint the $1$-st element red by spending one coin;
  4. decrease the $3$-rd element by $1$ and paint the $2$-nd element red.

Input

题意翻译

有一个长度为 $n$ 的数组 $a$，满足 $\forall a_i\in\{0,1,2\}$，一开始所有元素均为蓝色。 可以有如下操作： - 用一枚硬币，把一个蓝色元素涂成红色； - 选择一个不等于 $0$ 的红色元素和一个与其相邻的蓝色元素，将所选的红色元素减少 $1$，并将所选的蓝色元素涂成红色。 要将所有元素涂红，最少需要多少硬币？

Output

题目大意：
给定一个包含n个整数的数组，每个整数都是0、1或2。最初，数组中的每个元素都是蓝色的。目标是将数组的每个元素都涂成红色。为了实现这个目标，你可以执行两种类型的操作：
1. 花费一个硬币，选择一个蓝色元素并将其涂成红色；
2. 选择一个不为0的红色元素以及一个与之相邻的蓝色元素，将选定的红色元素减1，并将选定的蓝色元素涂成红色。

需要输出的是实现目标所需花费的最少硬币数量。

输入数据格式：
第一行包含一个整数n（1 ≤ n ≤ 2 × 10^5）。
第二行包含n个整数a_1, a_2, …, a_n（0 ≤ a_i ≤ 2）。

输出数据格式：
打印一个整数——为了将所有元素涂成红色，你必须花费的最少硬币数量。

示例：
输入
3
0 2 0
输出
1

输入
4
0 0 1 1
输出
2

输入
7
0 1 0 0 1 0 2
输出
4

注意：
在第一个示例中，你可以只花费一个硬币就能将所有元素涂成红色，操作如下：
1. 花费一个硬币将第二个元素涂成红色；
2. 将第二个元素减1，并将第一个元素涂成红色；
3. 将第二个元素减1，并将第三个元素涂成红色。

在第二个示例中，你可以只花费两个硬币就能将所有元素涂成红色，操作如下：
1. 花费一个硬币将第四个元素涂成红色；
2. 将第四个元素减1，并将第三个元素涂成红色；
3. 花费一个硬币将第一个元素涂成红色；
4. 将第三个元素减1，并将第二个元素涂成红色。题目大意： 给定一个包含n个整数的数组，每个整数都是0、1或2。最初，数组中的每个元素都是蓝色的。目标是将数组的每个元素都涂成红色。为了实现这个目标，你可以执行两种类型的操作： 1. 花费一个硬币，选择一个蓝色元素并将其涂成红色； 2. 选择一个不为0的红色元素以及一个与之相邻的蓝色元素，将选定的红色元素减1，并将选定的蓝色元素涂成红色。 需要输出的是实现目标所需花费的最少硬币数量。 输入数据格式： 第一行包含一个整数n（1 ≤ n ≤ 2 × 10^5）。 第二行包含n个整数a_1, a_2, …, a_n（0 ≤ a_i ≤ 2）。 输出数据格式： 打印一个整数——为了将所有元素涂成红色，你必须花费的最少硬币数量。 示例： 输入 3 0 2 0 输出 1 输入 4 0 0 1 1 输出 2 输入 7 0 1 0 0 1 0 2 输出 4 注意： 在第一个示例中，你可以只花费一个硬币就能将所有元素涂成红色，操作如下： 1. 花费一个硬币将第二个元素涂成红色； 2. 将第二个元素减1，并将第一个元素涂成红色； 3. 将第二个元素减1，并将第三个元素涂成红色。 在第二个示例中，你可以只花费两个硬币就能将所有元素涂成红色，操作如下： 1. 花费一个硬币将第四个元素涂成红色； 2. 将第四个元素减1，并将第三个元素涂成红色； 3. 花费一个硬币将第一个元素涂成红色； 4. 将第三个元素减1，并将第二个元素涂成红色。

Source/Category

加入题单

上一题 下一题 算法标签：