Ложные Зеркала. ты можешь помочь мне решить?

Question

Вот проблема

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

Можете ли вы помочь мне решить эту проблему? В чем сложность?

Answer 1

Проблема может быть решена с помощью DP.

После первого выстрела проблема больше не будет круговой. Урон монстров, оставшихся после атаки, можно рассчитать с помощью DP. Позволяет NB количество балконов.

Определите D[n,m] для n<=m или m+4<=n как урон монстров, оставленных на балконах 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).

Answer 2

Похоже, что ограничения проблемы таковы, что вы можете просто перебрать ее. В основном

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)

Вы также можете реализовать хит как битовую карту, а затем запомнить ее для ускорения функции.