Привет всем. Подскажите, как можно данную задачу более менее эффективно

решить?

В столовой одного известного Завода вот-вот начнётся обед. На обеде есть три гарнира — макарошки, пюрешка и греча. К гарнирам, конечно же, полагается горячее. Горячих блюд тоже три (ну и совпадение!) — сосиски, котлетки и кура. На раздаче сегодня стоит добрая повариха Алевтина Мстиславовна. Она немного ленива, но очень любит заводчан, вот перед ней и встала задача.

Итак, для начала поведаем вам прописные истины: макарошки лучше сочетать с сосисками, пюрешку с котлетками, а гречу с курой. Человек, у которого на обед одно из этих трёх сочетаний, будет счастливым, в противном случае счастливым он не будет.

На раздаче в очередь выстроились n заводчан. По очереди они будут подходить к Алевтине и называть ей гарнир, который они хотят. У Алевтины на раздаче будут все три гарнира, а также одно из горячих блюд. Заводчанину она будет выдавать гарнир, который он хочет, а также то горячее которое сейчас на раздаче. Кроме того, за всё время Алевтина готова не более чем k раз сходить в Горячий Цех и заменить горячее блюдо на раздаче на любое другое. Естественно, в начале она вольна принести на раздачу любое горячее блюдо, которое захочется.

Алевтина дружит со всеми заводчанами и уже заранее знает кому какой гарнир хочется. Всей информацией она поделилась с Вами. Алевтина добра душой и хочет, чтобы как можно больше заводчан были счастливы благодаря сочетанию гарнира и горячего. Ваша задача — сказать какое наибольшее число заводчан могут оказаться счастливыми при заданном ограничении на число замен горячего блюда на раздаче. Не подведите Алевтину!

В первой строке входных даны целые числа n и k (1⩽n⩽105, 0⩽k⩽20). В следующих n строках даны предпочтения по гарнирам в том порядке, в котором заводчане стоят в очереди, по одному на строке. Предпочтение описано одним из трёх символов: «M», «P» или «G» — макарошки, пюрешка или гречка соответственно.

Выведите какое наибольшее число заводчан будут счастливыми после обеда.

------------------------------

Примеры:
5 1
M
M
G
M
P
-> 4

Написал решение в лоб с использованием всех размещений с повторениями букв M, P, G. Но это очень неэффективно по времени

Тут дп dp[i][j][k] = v. сколько людей покушало, сколько перестановок горячего сделано, какое горячее сейчас стоит на раздаче, сколько было довольных

Сколько измерений получается? Я в дп не силен если честно.. Можете пожалуйста более подробно объяснить?

Измерений дп - 3. Асимптотика времени работы - O(n*k*3)

Получается максимизируем количество довольных. Целевая формула F(i, j, k). k - количество смен блюд, а i и j?

i - кол-во людей, которые успели пройти по очереди и что-то себе взять, j - кол-во смен блюд, k - текущее горячее блюдо, которое стоит на раздаче, v - кол-во довольных полученной едой людей

Если i-тый человек хочет гарнир x, dp[i][j][k] = max(dp[i-1][j][k] + 1 или dp[i-1][j-1][y(y!=x)] + 1 (в зависимости от k==x), dp[i-1][j][k])