假镜子。你能帮我解决吗？

发布于 2024-11-08 17:37:30 字数 455 浏览 0 评论 0原文

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

你能帮我解决这个问题吗？复杂程度如何？

原文

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

风轻花落早 2024-11-15 17:37:30

问题可以通过DP解决。

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

将 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)。

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

回复收藏 0 原文

傻比既视感 2024-11-15 17:37:30

看起来这个问题的限制是这样的，你可以用暴力来解决它。基本上，

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 实现为位图，然后将其存储以加速功能。

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.

回复收藏 0 原文

~没有更多了~