False Mirrors. can you help me to solve?

Here is the problem

BFG-9000 destroys three adjacent balconies per one shoot. (N-th balcony is adjacent to the first one). After the shoot the survival monsters inflict damage to Leonid (main hero of the novel) — one unit per monster. Further follows new shoot and so on until all monsters will perish. It is required to define the minimum amount of damage, which can take Leonid.

For example :

N = 8
A[] = 4 5 6 5 4 5 6 5

answer : 33
4 * * * 4 5 6 5 - 24
4 * * * * * * 5 - 9
* * * * * * * * - 0

Can you help开发者_C百科 me to solve this problem? What is the complexity?

Problem can be solved with DP.

After first shot problem will not be circular anymore. Damage of monsters that left after attack can be calculated with DP. Lets NB is number of balconies.

Define D[n,m] for n<=m or m+4<=nas damage of monsters left on balconies b, n<=b<=m or 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}.

Result is min{ D[i+3,NB+i-1] for i in {1,...,NB-2} }.

In third case and result indices are modulo NB.

This approach has complexity O(n^3).

It looks like the constraints of the problem are such that you can just brute force it . Basically

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)

You can also implement hit as a bit map and then memoize it to speed up the function.