← 返回题目列表

Codeforces · 1958/D

D. 楼梯

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

有一个楼梯,由 $$$n$$$ 级台阶组成。每一步要么完好无损,要么破损。对于每个损坏的步骤,给出一个整数 $$$a_i$$$ 表示修复它的难度。

每天,您可以:

- 修复任意损坏的步骤。修复第 $$$i$$$ 步骤所需的工作量等于 $$$a_i$$$;
- 或修复两个相邻损坏的台阶。修复第 $$$i$$$ 步骤和第 $$$(i+1)$$$ 步骤所需的工作量等于 $$$2 \cdot (a_i+a_{i+1})$$$。

您想要修复楼梯上所有破损的台阶,并且希望在尽可能短的时间内完成。在最少的天数内修复所有损坏的台阶至少需要多少工作量?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成:

- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 步数;
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^8$$$)。如果$$$a_i = 0$$$,则第$$$i$$$步不需要修复;否则,第$$$i$$$步骤被破坏,并且$$$a_i$$$是修复它的难度。

对输入的附加约束:$$$n$$$ 的值之和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 在最短的天数内修复所有损坏的步骤所需的最小可能的总工作量。

示例

输入 #1

6
5
0 0 0 0 0
4
0 13 15 8
4
13 15 0 8
8
1 2 3 4 5 6 7 8
5
99999999 100000000 99999999 99999999 99999999
5
2 3 4 3 2

输出 #1

0
59
64
72
899999993
24

注意

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

在第二个测试用例中,您可以在第一天修复 $$$3$$$-rd 和 $$$4$$$-th 步骤,并在第二天修复 $$$2$$$-nd 步骤。总工作量将为 $$$2 \cdot (15 + 8) + 13 = 59$$$。

在第三个测试用例中,您可以在第一天修复第 $$$4$$$ 步骤,并在第二天修复两个第一步。总工作量将为 $$$8 + 2 \cdot (13 + 15) = 64$$$。