Подход DP для расчета максимальной длины бус

Question

Я пытаюсь решить проблему с бисером USACO. В этой задаче вам дают цепочку бус, и вы должны найти максимально последовательную пару красных и синих бус.

Пример: ЕСЛИ вам дана строка wwwbbrwrbrbrrbrbrwrwwrbwrwrrbwwwbbrwrbrbrrbrbrwrwwrbwrwrrb, максимальная длина будет равна 11, так как вы разбиваете строку в эти два интервала wrwrrbwwwbb w считается как красный или синий шарик, в зависимости от того, что вам выгодно.

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

Пример: если бы мы использовали строку "rrbbwwrrb", мой возможный список счетчиков был бы [6,5] Мои различные разделы были бы rrbbww , bbwwrr и wwrrb .

Логически это кажется правильным решением, но это часть кода, которая ставит меня в тупик. Вот мой код:

neck = "wwwbbrwrbrbrrbrbrwrwwrbwrwrrbwwwbbrwrbrbrrbrbrwrwwrbwrwrrb"
n = len(neck)
maxi = -1 #max length
c = 0 #counter 
changes = 1 #number of color swaps
curr = 0 #each part

color = None

for i in range(n):
    if neck[i] == 'w':
        c += 1
        if changes == 2:
            curr += 1
    elif neck[i] == color:
        c += 1
        if changes == 2:
            curr += 1
    else:
        if changes == 3:
            color = neck[i]
            maxi = max(c,maxi)
            #print(str(c) + str(" ") + str(i))
            c = 1
            curr = 1
            changes = 1
        else:
            color = neck[i]
            c += 1
            if changes == 2:
                curr += 1
            changes += 1
print(maxi)

Правильный ответ - 11, но мое закодированное решение сообщает 9.

Answer 1

Я бы решил немного иначе и использовал бы рекурсию с возвратом. Это метод грубой силы, но он тщательный, и вы знаете, что получаете максимально возможное количество последовательных пар. Большая часть этого кода на самом деле находит пары, а не рекурсивность. Спасибо за головоломку!

def find_longest(s):
    pairs = []
    prev = ''
    for l in s:
        if l == prev:
            if len(pairs) > 1:
                pairs[len(pairs) - 2] += l
                pairs[len(pairs) - 1] += l
            elif len(pairs) == 1:
                pairs[len(pairs) - 1] += l
            else:
                pairs.append(l)
        else:
            if len(pairs) > 0:
                pairs[len(pairs) - 1] += l
                pairs.append(l)
            else:
                pairs.append(l)
        prev = l
    return max(pairs, key=len)

def solve():
    global beads
    global longest_found
    i = 0
    while i < len(beads):
        if beads[i] == 'w':
            for x in ['r', 'b']:
                beads[i] = x
                solve()
                beads[i] = 'w' #set back for next rounds
            return
        i += 1
    longest = find_longest("".join(beads))
    longest_found = longest if len(longest) > len(longest_found) else longest_found

beads = list("wwwbbrwrbrbrrbrbrwrwwrbwrwrrbwwwbbrwrbrbrrbrbrwrwwrbwrwrrb")
longest_found = ''
solve()

print("".join(beads))
print(len(longest_found), longest_found)

Результат:

wwwbbrwrbrbrrbrbrwrwwrbwrwrrbwwwbbrwrbrbrrbrbrwrwwrbwrwrrb
11 rrrrrbbbbbb

Answer 2

Основная идея c, которую вы, похоже, хотите реализовать, заключается в следующем:

• начинайте с любого места в ожерелье, следите за тем, какой цвет вы начнете
• подсчет бусин до тех пор, пока цвет не изменится дважды
• учитывает только изменение как 'b' или 'r' как измененное, игнорируя 'w'

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

Довольно наивная правильная реализация вашего подхода заключается в следующем. :

beads = "wwwbbrwrbrbrrbrbrwrwwrbwrwrrbwwwbbrwrbrbrrbrbrwrwwrbwrwrrb"
n = len(beads)
max_found = 0

for i in range(n):
    changed = False
    j = i
    current = beads[j]
    while True:
        if beads[j] not in [current, 'w']:
            if current != 'w':
                if changed:
                    break
                changed = True
            current = beads[j]
        j = (j + 1) % n
        if j == i:
            break

    found = (j - i) % n if j != i else n
    max_found = max(found, max_found)

    # this just just here to show progress, not critical to the algorithm
    if i < j:
        print(beads[i:j], found)
    else:
        print(beads[i:]+beads[:j], found)

print('Solution:', max_found)

Конечно, это возвращается слишком жадно, проверяя каждый возможный разрез ожерелья, даже если он может запомнить длину самой последней последовательности максимальной длины.

One способ сделать это - запомнить последнюю позицию, где был замечен первый цвет предыдущей последовательности, и вернуться сразу после нее, вместо того, чтобы начинать с каждой отдельной позиции, как указано выше. Вот это немного более сложное решение:

beads = "wwwbbrwrbrbrrbrbrwrwwrbwrwrrbwwwbbrwrbrbrrbrbrwrwwrbwrwrrb"
n = len(beads)
max_found = 0

c = 0
i = 0
while i < n:
    changed = False
    j = i
    current = beads[j]
    while True:
        if beads[j] not in [current, 'w']:
            if current != 'w':
                if changed:
                    break
                changed = True
            current = beads[j]
        if beads[j] == current and not changed:
            c = j + 1 if j >= c else n
        j = (j + 1) % n
        if j == i:
            break

    found = (j - i) % n if j != i else n
    max_found = max(found, max_found)

    # this just just here to show progress, not critical to the algorithm
    if i < j:
        print(beads[i:j], found)
    else:
        print(beads[i:]+beads[:j], found)

    # this line *is* part of the solution, but needs to happen after the prints
    i = c


print('Solution:', max_found)

Edit: @ Kri sh указал, что решение пропустило краевой случай, приведенный выше код был исправлен, поэтому алгоритм теперь также корректно обрабатывает beads = "rrr" .