Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1215. Забор
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 04/01/2004 | Областная олимпиада школьников по информатике (личное первенство) (5) |
| 18/02/2013 | Занятие 17 (D) |
| 06/07/2020 | Летние сборы - 4 (G) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (2)
Однажды тете Полли в голову пришла мысль сделать дома ремонт.
Начать она решила, конечно, с забора. "В прошлый раз ты прекрасно справился
с работой", – сказала тетя Полли Тому Сойеру, – "но сейчас модно красить
заборы не одним цветом, а несколькими цветами, чтобы получился красивый узор.
Вот тебе банки с краской, вот кисточка, вот образец из журнала, как надо
покрасить забор".
Том Сойер вышел на улицу и с тоской оглядел огромный забор. Из-за угла
появился Билли Гейл с удочкой и ведерком. "Что, старик, работать
приходится?" – спросил Билли. Том обернулся. "А ты хотел бы
немножко покрасить?" "А что ты мне за это дашь?" Том понял, что
Билли – единственный мальчик в городе, который не будет платить
за удовольствие покрасить забор. К счастью, у Тома оставалось еще
много вещей, полученных за предыдущую покраску забора. "У меня есть
бумажный змей, дохлая крыса на веревочке, губная гармоника,
ржавый ключ, …" "Хорошо", – прервал его Билли, – "я согласен, но ты
будешь отдавать мне одну вещь за каждую непрерывную полосу забора,
покрашенную одним цветом". Том решил придумать такой способ
покраски забора, чтобы отдать как можно меньше вещей алчному Билли.
Например, образец AABBCBBAA можно покрасить тремя полосами. Первый раз
макаем кисть в краску A и красим весь забор, получается AAAAAAAAA.
Далее макаем кисть в краску B и красим середину забора,
получается AABBBBBAA. И последний раз макаем в краску C и красим одну
доску в самой середине, получается AABBCBBAA.
В первой строке входного файла содержится число `N`
(`1\ ≤\ N\ ≤\ 20`) – количество образцов раскраски. В следующих `N` строках
даны образцы раскраски забора. Каждая строка содержит от 1 до 200 прописных
латинских букв. Одна буква соответствует одной доске забора. Различные цвета
обозначены различными буквами.
В выходной файл для каждого образца раскраски, заданного тетей Полли,
вывести на соответствующей отдельной строке минимальное количество вещей,
которое Том Сойер должен отдать Билли, чтобы раскрасить
забор по этому образцу.
Пример ввода
2 AABBCBBAA ABCD
Пример вывода
3 4
