#P4922. [Lydsy1706月赛]Karp-de-Chant Number

    ID: 4027 传统题 1000ms 256MiB 尝试: 744 已通过: 181 难度: 7 上传者: 标签>难度分类提高排序与序列处理自定义排序规则贪心交换论证动态规划0/1 背包滚动数组CF2200本OJ付费获取

[Lydsy1706月赛]Karp-de-Chant Number

题目描述

卡常数被称为计算机算法竞赛之中最神奇的一类数字,主要特点集中于令人捉摸不透,有时候会让水平很高的选手迷之超时。

普遍认为卡常数是埃及人Qa'a及后人发现的常数。也可认为是卡普雷卡尔(Kaprekar)常数的别称。主要用于求解括号序列问题。

据考证,卡(Qa'a)是古埃及第一王朝的最后一位法老。他发现并研究了一种常数,后世以他的名字叫做卡常数。卡特兰数的起源也是因为卡的后人与特兰克斯结婚,生下来的孩子就叫卡特兰,而他只是发表了祖传的家书而已。Sereja也是卡的后人,提出括号序列问题,也是从家书里得到的资料。然而Sereja为了不让这个秘密公开,于是隐瞒了这道题的真正做法。可是由于卡的后人不是各个都像卡特兰一样爱慕虚荣,这一算法也无法找到。“欲见贤人而不以其道,犹欲其入而闭之门也”。卡之常数的奥秘,需要以一颗诚心去追寻。

现给定 nn 个括号序列。你可以选出若干序列,每个序列至多选一次,并按任意顺序将它们从左到右拼接起来。求能得到的合法括号序列的最大长度。合法括号序列的每个前缀中,左括号数不少于右括号数,且整个序列的左右括号数相等。

输入格式

第一行包含一个正整数 nn,满足 1≤n≤3001\le n\le 300。

接下来 nn 行,每行包含一个长度在 [1,300][1,300] 内的序列,仅由左、右小括号组成。

输出格式

输出一行一个整数,表示最大长度。可以一个序列也不选,此时长度为 00。

样例

3
())
((()
)()
10

样例解释

按编号 2,1,32,1,3 的顺序拼接得到 ((()()))(),总长度为 1010。