假镜子.你能帮我解决吗?

Question

这是问题所在

BFG-9000 每次拍摄会破坏三个相邻的阳台。（第N个阳台毗邻 第一个）。射击后，生存怪物对列昂尼德造成伤害 （小说的主要英雄）——每个怪物一个单位。进一步跟进新拍摄等 直到所有的怪物 会灭亡。需要定义最小损坏量， 可以带走列昂尼德。

例如：

N = 8
A[] = 4 5 6 5 4 5 6 5
answer : 33
4 * * * 4 5 6 5 - 24
4 * * * * * * 5 - 9
* * * * * * * * - 0

你能帮我解决这个问题吗？复杂性是什么？

Answer 1

问题可以用DP解决。

第一次射击后问题将不再循环。攻击后留下的怪物的伤害可以用DP计算。让我们NB是阳台的数量。

将n<=m或m+4<=n的D[n,m]定义为留在阳台上的怪物的伤害 b 、n<=b<=m或m<=b<=n。

If n <= m < n+3 than D[n,m] = sum A[i] for n<=i<=m.
If m >= n+3 than D[n,m] =
   min{ 2*D[n,i-1] + D[i,i+2] + 2*D[i+3,m] } for i in {n,...,m}.
If m < n than D[n,m] =
   min{ 2*D[n,i-1] + D[i,i+2] + 2*D[i+3,m] } for i in {n,...,NB} U {1,...,m}.

结果是 min{ D[i+3,NB+i-1] for i in {1,...,NB-2} } 。

在第三种情况下，结果指数是模NB。

这种方法具有复杂性O(n^3)。

Answer 2

看起来问题的约束是如此之大，以至于您可以暴力破解它。 基本上

def go(hit):
    res = 999 
    #base case, check if all items in hit are true.
    for i in range(len(hit)):
        if not hit[i]:
             newhit = [x for x in hit]
             newhit[i] = newhit[i-1] = newhit[(i+1)%len(hit)] = True; 
             damage = 0;
             for j in range(len(hit)):
                  if not newhit[j]:
                     damage+=hit[j]
             res = min(res, go(newhit)+damage)

您还可以将 hit 实现为位图，然后记住它以加快功能。