下面是问题

BFG-9000会破坏每拍三个相邻的阳台。 （第N阳台相邻       第一个）。拍摄后存活的怪物造成伤害列昂尼德       （主要小说英雄） - 每个怪物的一个单位。进一步如下新梢等       直到所有的怪物       将灭亡。它需要定义损坏的最小量，       这可能需要狮子座。

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.

例如：

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?

推荐答案

就可以解决问题与DP。

Problem can be solved with DP.

在第一枪的问题将不会是圆形了。妖怪攻击后留下的损伤，可以计算具有DP。让 NB 是阳台的数量。

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.

定义 D [N，M] 为 N'LT; = M 或 M + 4℃= N 左阳台上的怪物伤害 B ， N'LT; = B＆LT; = M 或 M＆LT; = B＆LT;。= N

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

结果是分钟{D [i + 3中，NB + I-1]我在{1，...，NB-2}} 。

在第三种情况和结果指数模NB。

In third case and result indices are modulo NB.

该方法具有复杂性为O（n ^ 3）。