← 返回题目列表

Codeforces · 1795/E

E. 爆炸?

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

您正在玩另一款使用魔法杀死怪物的游戏。该行中有 $$$n$$$ 个单元格,编号从 $$$1$$$ 到 $$$n$$$。最初,第 $$$i$$$ 个单元格包含具有 $$$h_i$$$ 生命值的第 $$$i$$$ 个怪物。

你有一个基本法术,消耗$$$1$$$ MP并对你选择的怪物造成$$$1$$$伤害。您可以施放任意次数。此外,你还有一个带有“爆炸”法术的特殊卷轴,你只能使用一次。你想用爆炸来完成杀怪,所以你首先施放几次基础法术(可能是零次),然后施放一次“爆炸”。

“爆炸”咒语如何发挥作用?首先,你选择法术的威力:如果你将$$$x$$$ MP倒入其中,“爆炸”将造成$$$x$$$伤害。其次,你选择一些怪物$$$i$$$,它将成为法术的目标。这就是接下来发生的事情:

- 如果其当前生命值 $$$h_i > x$$$,那么他仍然活着,生命值减少了 $$$x$$$;
- 如果$$$h_i \le x$$$,则第$$$i$$$个怪物会因爆炸而死亡,对相邻单元格$$$i - 1$$$和$$$i + 1$$$中的怪物造成$$$h_i - 1$$$伤害,如果这些单元格存在并且里面的怪物仍然活着;
- 如果爆炸造成的伤害足以杀死怪物$$$i - 1$$$(或$$$i + 1$$$),i。 e.当前的$$$h_{i - 1} \le h_i - 1$$$(或$$$h_{i + 1} \le h_i - 1$$$),那么该怪物也会死亡,并产生二次能量爆炸$$$h_{i-1} - 1$$$(或$$$h_{i+1} - 1$$$),可能对其邻居造成伤害,依此类推,直到爆炸结束。

你的目标是通过这些“连锁”爆炸杀死所有剩余的怪物,这就是为什么你需要一个基本法术来减少某些怪物的$$$h_i$$$,甚至提前杀死它们(当怪物当前的生命值$$$h_i$$$变得小于或等于零时,怪物就会死亡)。请注意,怪物不会在单元格之间移动,因此,例如,怪物 $$$i$$$ 和 $$$i + 2$$$ 永远不会成为邻居。

以你想要的方式杀死所有怪物所需的最低总 MP 是多少?总 MP 计算为您施展的基本法术数量与您选择的爆炸卷轴的威力 $$$x$$$ 之和。

输入

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

每个测试用例的第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) - 行中的单元格数量,i。 e.怪物的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 10^6$$$) — 怪物的初始生命值。

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

输出

对于每个测试用例,打印一个整数 - 通过爆炸杀死所有怪物所需的最小总 MP。

示例

输入 #1

5
3
1 1 1
4
4 1 2 1
4
5 10 15 10
1
42
9
1 2 3 2 2 2 3 2 1

输出 #1

3
6
15
42
12

注意

在第一个测试用例中,例如,您可以对怪物 $$$1$$$ 和 $$$2$$$ (每个怪物一次)使用基本法术来杀死它们。之后,你对怪物$$$3$$$施放“爆炸”力量$$$x = 1$$$来杀死它。您需要的 MP 总数为 $$$2 + 1 = 3$$$。

在第二个测试用例中,最好对怪物 $$$1$$$ 施展基本法术 $$$4$$$ 次来杀死它。之后,你可以对怪物$$$3$$$施放能量$$$x = 2$$$的“爆炸”。它死亡后,会产生能量爆炸 $$$1$$$,杀死怪物 $$$2$$$ 和 $$$4$$$。您需要的总 MP 为 $$$4 + 2 = 6$$$。

在第三个测试用例中,你对怪物 $$$3$$$ 施放了能量 $$$15$$$ 的“爆炸”。 $$$3$$$-rd 怪物爆炸(力量为 $$$14$$$)杀死怪物 $$$2$$$ 和 $$$4$$$。怪物$$$2$$$的二次爆炸(力量$$$9$$$)杀死了怪物$$$1$$$。