Правильная скобочная последовательность (или, коротко, ПСП) — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы «1» и «+» между исходными символами. Например:
Обозначим конкатенацию двух строк $$$x$$$ и $$$y$$$ как $$$x+y$$$. Например, «()()» $$$+$$$ «)(» $$$=$$$ «()())(».
У вас есть $$$n$$$ скобочных последовательностей $$$s_1, s_2, \dots, s_n$$$. Вы можете переставить эти строки в любом порядке (можно переставлять только сами строки, но не символы в них).
Ваша задача — переставить строки в таком порядке, чтобы у строки $$$s_1 + s_2 + \dots + s_n$$$ было как можно больше непустых префиксов, являющихся ПСП.
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 20$$$).
Далее следуют $$$n$$$ строк, $$$i$$$-я из которых содержит $$$s_i$$$ — скобочную последовательность (строку, состоящую из символов «(» и/или «)». Все последовательности $$$s_i$$$ непустые, их суммарная длина не превосходит $$$4 \cdot 10^5$$$.
Выведите одно число — максимальное количество непустых префиксов, являющихся ПСП, у строки $$$s_1 + s_2 + \dots + s_n$$$, если вы переставите строки $$$s_1, s_2, \dots, s_n$$$ оптимальным образом.
2 ( )
1
4 ()()()) ( ( )
4
1 (())
1
1 )(()
0
В первом примере из условия можно склеить строки следующим образом: «(» $$$+$$$ «)» $$$=$$$ «()», у полученной строки будет один префикс, являющийся ПСП: «()».
Во втором примере из условия можно склеить строки следующим образом: «(» $$$+$$$ «)» $$$+$$$ «()()())» $$$+$$$ «(» $$$=$$$ «()()()())(», у полученной строки будет четыре префикса, являющихся ПСП: «()», «()()», «()()()», «()()()()».
В третьем и в четвертом примере всего по одной строке, поэтому поменять порядок строк невозможно.
Название |
---|