N. Удаление скобок

Дана строка из круглых, квадратных и фигурных скобок. Удалите наименьшее число символов так, чтобы оставшиеся образовали правильную скобочную последовательность, и выведите то, что осталось.

Правильная последовательность определяется обычно: пустая строка правильна; если $A$ правильна, то $(A)$, $[A]$ и $\{A\}$ правильны; если $A$ и $B$ правильны, то и $AB$ правильна.

Динамика

$dp[i][j]$ - наибольшая длина правильной подпоследовательности внутри $s[i..j]$. Переходов два вида, и оба нужны:

Сомкнуть края. Если $s_i$ и $s_j$ - парные скобки, можно взять их обе: $dp[i+1][j-1] + 2$.

Разрезать. Для любого $k$: $dp[i][k] + dp[k+1][j]$.

Только первого перехода мало: строка ()[] разбивается на две части, и никакого смыкания краёв в ней нет. Только второго тоже мало: ([]) смыканием берётся целиком, а любым разрезом - нет.

Восстановление

Ответ - сама строка, значит одной таблицы длин недостаточно: надо помнить, каким переходом получено каждое состояние.

Хранить в $dp[i][j]$ саму строку - соблазнительно и смертельно: строк $700^2$, каждая до 700 символов, это гигабайты. Хранить надо решение: одно число, говорящее «сомкнули края» или «разрезали в точке $k$».

if (choice[i][j] == -1) { answer += s[i]; build(i + 1, j - 1); answer += s[j]; }
else { build(i, choice[i][j]); build(choice[i][j] + 1, j); }

В оригинальной постановке этой задачи ограничение по памяти было 8 мегабайт - ровно затем, чтобы отсечь решения, хранящие строки в таблице. Здесь лимит мягче, но привычка хранить решение, а не результат, стоит дороже пройденного теста.

Если правильных ответов несколько, подойдёт любой.

Подробнее: «Восстановление ответа», «Динамика по подотрезкам».

Одна строка из круглых, квадратных и фигурных скобок. Длина не превосходит 700.

Строка наибольшей длины, являющаяся правильной скобочной последовательностью и получающаяся из исходной удалением символов. Если ответов несколько, выведите любой. Если подходит только пустая строка, выведите пустую строку.