← 返回题目列表

Codeforces · 1418/C

C. 真人快打塔

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

您和您的朋友正在玩真人快打 XI 游戏。你正试图通过挑战塔。这座塔里有$$$n$$$个boss,编号从$$$1$$$到$$$n$$$。第 $$$i$$$ 个 boss 的类型是 $$$a_i$$$。如果第$$$i$$$个boss很简单,那么它的类型是$$$a_i = 0$$$,否则这个boss很困难,它的类型是$$$a_i = 1$$$。

在一个会话中,您或您的朋友可以杀死一到两个 Boss(您和您的朋友都不能跳过该会话,因此在一个会话中杀死的 Boss 数量最少为 1 个)。在您的朋友会话之后,您的会话开始,然后您的朋友会话再次开始,您的会话开始,依此类推。第一个会话是您朋友的会话。

你的朋友需要变得更好,因为他实际上无法杀死强硬的老板。为了杀死他们,他使用了跳跃点。一个跳跃点可以用来杀死一个硬boss。

你的任务是找到你的朋友需要使用的最小跳跃点数量,以便你和你的朋友按照给定的顺序杀死所有 $$$n$$$ 老板。

例如:假设 $$$n = 8$$$,$$$a = [1, 0, 1, 1, 0, 1, 1, 1]$$$。那么最好的行动方案如下:

- 你的朋友杀死了两个第一个boss,对第一个boss使用了一个跳跃点;
- 你杀死了第三个和第四个 Boss;
- 你的朋友杀死了第五个boss;
- 你杀死了第六个和第七个 Boss;
- 你的朋友使用一个跳跃点杀死了最后一个boss,因此塔使用两个跳跃点完成。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — boss 的数量。测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个 boss 的类型。

保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。

输出

对于每个测试用例,打印答案:您的朋友需要使用的最小跳跃点数,以便您和您的朋友按给定顺序杀死所有 $$$n$$$ 老板。

示例

输入 #1

6
8
1 0 1 1 0 1 1 1
5
1 1 1 1 0
7
1 1 1 1 0 0 1
6
1 1 1 1 1 1
1
1
1
0

输出 #1

2
2
2
2
1
0