← 返回题目列表

Codeforces · 1990/D

D. 网格拼图

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

给你一个大小为 $$$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

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

0
3
2
1
2
2
3
2
4
6

注意

在第一个测试用例中,您不需要执行任何操作。

在第二个测试用例中,您可以执行以下操作:

- 将 $$$(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$$$是最少的操作次数。