CF1990D Grid Puzzle

题目描述

给定一个大小为 $n$ 的数组 $a$ 。

有一个 $n \times n$ 的网格。在第 $i$ 行，前 $a_i$ 个格子是黑色的，其余格子是白色的。也就是说，记 $(i,j)$ 为第 $i$ 行第 $j$ 列的格子， $(i,1), (i,2), \ldots, (i,a_i)$ 这些格子是黑色的， $(i,a_i+1), \ldots, (i,n)$ 这些格子是白色的。

你可以进行如下任意次数、任意顺序的操作：

将一个 $2 \times 2$ 的子网格染成白色；
将整行染成白色。注意你不能将整列染成白色。

请你求出将所有格子染成白色所需的最少操作次数。

输入格式

第一行包含一个整数 $t$ （ $1 \leq t \leq 10^4$ ），表示测试用例的数量。

对于每个测试用例：

第一行包含一个整数 $n$ （ $1 \leq n \leq 2 \cdot 10^5$ ），表示数组 $a$ 的大小。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $0 \leq a_i \leq n$ ）。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出一个整数，表示将所有格子染成白色所需的最少操作次数。

输入输出样例 #1

输入 #1

10
1
0
4
2 4 4 2
4
3 2 1 0
3
0 3 0
3
0 1 3
3
3 1 0
4
3 1 0 3
4
0 2 2 2
6
1 3 4 2 0 4
8
2 2 5 2 3 4 2 4

输出 #1

说明/提示

在第一个测试用例中，你不需要进行任何操作。

在第二个测试用例中，你可以进行如下操作：

将 $(1,1), (1,2), (2,1), (2,2)$ 染成白色；
将 $(2,3), (2,4), (3,3), (3,4)$ 染成白色；
将 $(3,1), (3,2), (4,1), (4,2)$ 染成白色。

可以证明 $3$ 是最少的操作次数。

在第三个测试用例中，你可以进行如下操作：

将第一行染成白色；
将 $(2,1), (2,2), (3,1), (3,2)$ 染成白色。

可以证明 $2$ 是最少的操作次数。

由 ChatGPT 4.1 翻译

#CF1990D. Grid Puzzle

Grid Puzzle