Олимпиадный тренинг

Задача . Video Game


Задача

Темы: Динамическое программирование Конечные автоматы реализация

Беси играет в видеоигру. В этой игре 3 буквы 'A', 'B', 'C' - все управление. Эти буквы можно нажимать в любом порядке, однако возможны только N (1<=N<=20) различных комбинаций. Комбинация I представлена строкой Si с длиной от 1 до 15 символов, содержащей только символы 'A', 'B', 'C'.
Когда Беси нажимает комбинацию букв, соответствующую какой-то из введенных строк, она получает один балл. Комбинации могут перекрываться и даже заканчиваться одновременно. Например, если N=3 и три возможные комбинации есть "ABA", "CB" и "ABACB", а Беси набрала ABACB, она получит 3 балла. Беси может получать очко за каждую комбинацию более чем один раз.
Беси конечно хочет заработать как можно больше баллов. Если она нажмет ровно K (1<=K<=1000) клавиш, какое максимальное количество баллов она может заработать?
PROBLEM NAME: combos
Формат входных данных
* Строка 1:Два разделенных пробелом целых числа: N и K.
* Строки 2..N+1: Строка i+1 содержит только одну строку Si, представляющую комбинацию i.
Формат выходных данных
* Строка 1: Одно целое число, максимальное количество баллов, которое может набрать Беси


Примечание
Оптимальная последовательность клавиш есть ABACBCB, которая дает 4 балла 1 от ABA, 1 от ABACB, и 2 от CB.


Примеры
№Входные данныеВыходные данные
1 
3 7
ABA
CB
ABACB
 
4
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет