Итак, программисты, у меня к вам очень любопытная задача, алгоритма решения которой, к сожалению, я не достиг=(
Надеюсь на вашу помощь и здравомыслящий ум))
Удаление скобок
Дана строка, составленная из круглых, квадратных и фигурных скобок. Определите, какое наименьшее количество символов необходимо удалить из этой строки, чтобы оставшиеся символы образовывали правильную скобочную последовательность.
Входные данные Строка из круглых, квадратных и фигурных скобок. Длина строки не превосходит 100 символов.
Выходные данные Выведите строку максимальной длины, являющуюся правильной скобочной последовательностью, которую можно получить из исходной строки удалением некоторых символов.Если возможных ответов несколько, выведите любой из них.
Примеры
входные данные ([)]
выходные данные
[]
входные данные
{([(]{)})]
выходные данные
[({})]
Автокомментарий: текст был обновлен пользователем MacKenlly (предыдущая версия, новая версия, сравнить).
Обычная динамика по подотрезкам:
dp[l][r] — ответ для подотрезка [l;r].
Как делать переход?
Во-первых, последовательность может быть конкатенацией 2 правильных, тогда ответ — это dp[l][k]+dp[k+1][j] для всех k.
Во-вторых, это может быть что-то типа (А). Тогда ответом может быть dp[l+1][r] + 1 или dp[l][r-1] + 1. Кроме того, если l и r — хорошие скобки, то ещё и dp[l+1][r-1].
Из всех возможных вариантов берём минимум
МОЗГ) Спасибо за помощь. Одному трудно учиться(
http://acm.timus.ru/problem.aspx?space=1&num=1183