假镜子。你能帮我解决？

问题描述

下面是问题

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

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

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）。

这篇关于假镜子。你能帮我解决？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！