False Mirrors. can you help me to solve?

Question

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 me to solve this problem? What is the complexity?

Answer 1

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).