I. Длина правильной подпоследовательности

2000 мс · 256 МБ · всё или ничего

Как классная задача про скобки, но выводить надо только длину наибольшей правильной подпоследовательности.

Восстановление отпадает, а значит отпадает и таблица решений - остаётся одна таблица длин. Это ровно то, ради чего стоит уметь отделять «что мы храним» от «что мы выводим»: памяти становится вдвое меньше, а код короче.

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

dp[i][j] = \max\Bigl(dp[i+1][j],\ \max_{k:\ s_i \text{ парен } s_k} \bigl(dp[i+1][k-1] + 2 + dp[k+1][j]\bigr)\Bigr)

Такая запись не даёт выигрыша в асимптотике - она по-прежнему $O(n^3)$ , - но избавляет от лишнего перебора разрезов и заметно уменьшает константу.

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

Формат ввода

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

Формат вывода

Одно число - длина наибольшей правильной скобочной подпоследовательности.

Примеры

ввод

([)]

вывод

ввод

)(

вывод

Войдите, чтобы отправлять решения.