Трехсимвольные машины

[Nikys]

Всем добрый вечер! Понадобилось решить следующую задачу.
Пусть мы имеем машину, которая принимает на вход буквы A, B и C. После каждой принятой буквы машина смотрит на последние три буквы (включая эту) и возвращает:

• 0, если у нас либо все буквы A, либо все буквы B, либо все все буквы C
• 2, если содержатся все три буквы A, B, C
• 1 во всех остальных случаях

Пока у нас меньше трех символов прошло через машину, то правила аналогичны (для одного символа всегда работает первое правило, а для двух - либо первое, либо третье).
Собственно, дается заранее полностью известная последовательность символов из алфавита {A,B,C} и две машины, которые работают вышеописанным образом.
Задача состоит в том, чтобы распределять каждый следующий символ между двумя данными машинами, чтобы сумма всех выводов из первой и второй машины была максимальной.

Собственно, брутфорс-перебор довольно очевиден: делать две пары копий машин, в первой паре символ подать на первую машину, во второй паре - на вторую машину, и запустить такой же алгоритм для каждой пары машин для новой последовательности символов (та же, но без первого символа) и выделить ту пару, где сумма будет больше. Но это, во-первых, крайне медленно (очевидно, $O(2^n)$), во-вторых, много памяти, рекурсия и вообще некрасиво.

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

Может ли кто-то подкинуть мысль о чем стоит задуматься, ну, или что почитать, если есть подобного рода классы задач? Заранее всем спасибо.

[Sphinx Pinastri]

Можно почитать про динамическое программирование здесь: http://informatics.mccme.ru/course/view.php?id=9
Там же можно и порешать задачи по теме с автоматической проверкой.

[Nikys]

Sphinx Pinastri
Ну, про динамику я тоже до этого думал, но я не сильно, во-первых, представляю как её тут реализовать, и к тому же это тоже, я так понял, сведется так или иначе к перебору. Но все же, хотелось бы найти здесь определенного рода стратегию в распределении.

[12d3]

Идея динамического программирования: сформулировать как-то подзадачу и найти связь между "соседними" подзадачами. Для начала будем считать, что в выводе обеих машин изначально присутствует два символа $D$. Это чтобы сформулировать выражение

Nikys в сообщении #1075839 писал(а):

После каждой принятой буквы машина смотрит на последние три буквы (включая эту) и возвращает:
0, если у нас либо все буквы A, либо все буквы B, либо все все буквы C
2, если содержатся все три буквы A, B, C
1 во всех остальных случаях
Пока у нас меньше трех символов прошло через машину, то правила аналогичны (для одного символа всегда работает первое правило, а для двух - либо первое, либо третье).

таким образом: после добавления символа в машину она выводит количество различных символов из алфавита $\{A,B,C\}$ среди последних трех символов в машине минус единица.
Подзадачу сформулируем таким образом: найти максимальную сумму выводов машин после скармливания им $m$ символов из нашей строки, чтобы последние два символа первой машине равнялись $a_1$ и $a_2$, а во второй машине $b_1,b_2$. Обозначим такую функцию как $f(m,a_1,a_2,b_1,b_2)$. Начальные условия: $f(0,a_1,a_2,b_1,b_2) = \begin{cases}{0,& if \,\,a_1=a_2=b_1=b_2=D\\-\infty,& other\,cases}\end{cases}$. За "минус бесконечность" можете взять просто достаточно большое отрицательное число. Логически это означает, что данная ситуация невозможна, а в программе так делается, чтобы не обрабатывать по отдельности возможные и невозможные ситуации.
Связь между "соседними" подзадачами: обозначим через $x_i, i \in \{1,...,n\}$ входную строку.
$f(m,a_1,a_2,b_1,b_2) = \begin{cases}{\max \limits_{y \in \{A,B,C\}}(f(m-1,y,a_1,b_1,b_2) + d(y,a_1,a_2)),& if\, a_2 = x_m\\\max \limits_{y \in \{A,B,C\}} (f(m-1,a_1,a_2,y,b_1)+d(y,b_1,b_2)),& if\, b_2 = x_m}\\-\infty,& other\,cases \end{cases}$
Здесь через $d(a,b,c)$ обозначено количество различных символов из алфавита $\{A,B,C\}$ среди $a,b,c$ минус единица.
Если у нас $a_2=b_2=x_m$, то из этих двух максимумов берем наибольший.
То, что нам надо найти в исходной задаче, это $\max \limits_{a_1,a_2,b_1,b_2 \in \{A,B,C,D\}} f(n,a_1,a_2,b_1,b_2)$
Этого должно хватить для решения задачи.