CF1795E Explosions?

### 题目大意 你在玩一个利用魔法杀怪物的游戏。具体地，有一排 $n$ 个格子，第 $i$ 个格子里有编号为 $i$、初始生命值为 $h_i$ 的怪物。怪物生命值小于等于 $0$ 则被杀死，所有怪物被杀死则游戏结束。 你有两种攻击方式：一种是普通攻击，你将消耗 $1$ 点能量对选中的怪物进行 $1$ 点伤害（也就是怪物的生命值减 $1$），你可以使用普通攻击任意次数。同时，你还可以使用恰好一次“爆炸”攻击。你想要游戏以“爆炸”攻击结束，也就是说，你会先进行若干次普通攻击（可以为 $0$ 次），然后使用一次“爆炸”攻击结束游戏。 “爆炸”攻击的机制如下：你可以选择消耗的能量数 $x$，然后选中一个怪物 $i$，之后： - 若怪物 $i$ 当前的生命值 $h_i > x$，那么该怪物生命值减去 $x$； - 若 $h_i\le x$，则该怪物被击杀，同时向两旁的怪物（即第 $i-1$ 和 $i+1$ 只怪物，如果有且还存活的话）造成 $h_i - 1$ 的伤害； - 若 $h_i - 1$ 的伤害足以杀死第 $i-1$ （或 $i+1$）只怪物，即 $h_{i-1}\le h_i - 1$（或 $h_{i+1}\le h_i - 1$），那么这只怪物同样被击杀并向两旁的怪物造成 $h_{i-1} - 1$（或 $h_{i+1} - 1$）的伤害。如此循环只到杀不死一直怪物为止。 你的目标就是先用普通攻击减少某些怪物的生命值或直接杀死某些怪物，然后用这样“链式”的“爆炸”攻击杀死所有怪物。注意怪物不会移动，例如第 $i$ 只怪物和第 $i+2$ 只怪物永远不会相邻。 你需要消耗最少的能量值来达成目标（包括普通攻击和“爆炸”攻击的），求出这个最小值。

无

无

In the first test case, you can, for example, use basic spell on monsters $ 1 $ and $ 2 $ (once per monster) to kill them. After that, you cast "Explosion" of power $ x = 1 $ on monster $ 3 $ to kill it. The total MP you need is $ 2 + 1 = 3 $ . In the second test case, it's optimal to cast basic spell $ 4 $ times onto monster $ 1 $ to kill it. After that, you can cast "Explosion" of power $ x = 2 $ onto monster $ 3 $ . It dies, creating an explosion of power $ 1 $ that kills monsters $ 2 $ and $ 4 $ . The total MP you need is $ 4 + 2 = 6 $ . In the third test case, you cast "Explosion" of power $ 15 $ onto monster $ 3 $ . Explosion of the $ 3 $ -rd monster (of power $ 14 $ ) kills monsters $ 2 $ and $ 4 $ . Secondary explosion of monster $ 2 $ (of power $ 9 $ ) kills monster $ 1 $ .