algorithm - 杀死每个弓箭手所需的最少火球数量？

Question

Polycrap 想要杀死一排弓箭手，他唯一的武器是火球。如果 Polycarp 用他的火球击中第 i 个弓箭手(他们从左到右编号)，弓箭手将失去 a 生命值。

同时该法术会伤害与第 i 个相邻的弓箭手(如果有的话)——他们失去 b (1 ≤ b < a ≤ 10) 生命值每个点。

由于极限弓箭手(即编号为1和n的弓箭手)距离很远，火球无法到达他们。 Polycarp 可以用他的火球击中任何其他弓箭手。

每个弓箭手的健康点数是已知的。当此数量小于 0 时，弓箭手将被杀死。Polycarp 可以使用的最小法术数量是多少？

如果射手已经被杀死，Polycarp 可以将他的火球扔向射手。

I/O 说明

INPUT -The first line of the input contains three integers n, a, b (3 ≤ n ≤ 10; 1 ≤ b < a ≤ 10). 
       The second line contains a sequence of n integers — h1, h2, ..., hn (1 ≤ hi ≤ 15), where hi is the amount of health points the i-th archer has.

OUTPUT- In the first line print t — the required minimum amount of fire balls.
        In the second line print t numbers — indexes of the archers that Polycarp should hit to kill all the archers in t shots. 

现在我编写了一个递归函数，它获取弓箭手当前生命值的数组并生成每个可能的攻击，直到所有弓箭手都死了并返回最小值。

但是这种方法太慢了，如何高效解决呢？

注意:我不一定对优化自己的解决方案感兴趣，但对可能更快的任何其他解决方案持开放态度。

Problem Link with some test cases

My current solution

Answer 1

关键是要杀死最左边的弓箭手，你需要通过火球攻击他或他旁边的弓箭手。

1. 杀死第 1 个和第 n 个弓箭手。
2. 从左边开始。你可以通过向他或他右边的同伴 throw 火球来杀死最左边的弓箭手。安排数组 DP，其中将包含诸如剩余弓箭手数量和最左边三个人的生命值(AD 中其他人的生命值)之类的条目。因此，尝试两种可能性中的一种，检查您是否已经处于这种情况，如果是，使用来自 DP 的答案，如果没有递归向下，然后展开递归，在递归的每个级别上将数据添加到数组 DP 中。