Description

外星人制造了超级电脑来思考生命, 宇宙, 以及世界万物的答案, 最后得出了 42 这个结果. 人们并不满意于这个答案, 于是再一次设计了超级电脑. 经历了 \(\pi\) 百万年的计算, 再一次得出了新的答案. 答案是由一些字符串组成的, 每个字符串都只包含 ( 和 ) 两种字符. 现在的问题是, 从这些字符串中选取一些, 按照一定的顺序连接起来, 使得构成一个合法的括号序列而且长度尽量长.

Input

本题存在多组数据, 请做到文件底结束, 任两组数据间存在一空行.

在每组数据中, 第一行一个正整数 \(n\), 表示字符串个数.

接下来 \(n\) 行每行一个字符串. 总长度不超过 \(10000\).

Output

对于每组数据, 输出生成的括号序列的最大长度.

Sample Input

3
()
(()
)

Sample Output

6

Data Range

对于所有的数据, 满足:\(1 \leq n \leq 1000\).

Explanation

贪心地讲, 我们发现一个括号串中间括号的分布对结果是没有影响的. 有影响的是一个括号中有几个开括号, 几个闭括号; 有多少个左边强行关闭 (即没有开括号配对的) 闭括号, 右边 多少个强行打开的开括号. 将这些值维护以后, 我们开始贪心.

膜拜 hld67890 口头 AC 题解......

优先选择全开的括号串, 最后选择全闭的括号串.

然后在半开半闭的括号串中 dp, 优先选择开的更多的.

然而我觉得应该直接贪心, 然后 sort 了一下进行了一个 dp 过了, 但是并不明白怎么回事 QwQ

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define maximize(__x,__y) __x=max(__x,__y)
#define max_3(__x,__y,__z) max(max(__x,__y),__z)
using namespace std;
typedef long long lli;
const int maxn = 1010, maxm = 10010;
const int infinit = 0x3f3f3f3f;

struct parthstr { int lbrac, rbrac, pairs; }; // Parentheses in strings
bool operator < (parthstr a, parthstr b) {
    bool ba = a.lbrac >= a.rbrac,
         bb = b.lbrac >= b.rbrac;
    if (ba != bb) {
        return ba > bb;
    } else {
        if (ba) return a.rbrac < b.rbrac;
        else return a.lbrac > b.lbrac;
    }
    return false;
} parthstr ps[maxn];

int n;
char str[maxm];
int dp[2][maxm];

int main(int argc, char** argv)
{
    while (scanf("%d", &n) != EOF) {
        // Clearing previous data for intactness.
        memset(ps, 0, sizeof(ps));
        memset(str, 0, sizeof(str));
        memset(dp, 0, sizeof(dp));
        // Read the strings and abandon the rest.
        int sumlen = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%s", str + 1);
            int len = strlen(str + 1);
            int lbrac = 0, // Unclosed left parentheses
                rbrac = 0, // Unclosed right parentheses
                pairs = 0; // Created pairs
            for (int j = 1; j <= len; j++) {
                if (str[j] == '(') {
                    lbrac += 1;
                } else {
                    if (lbrac == 0)
                        rbrac += 1;
                    else
                        lbrac -= 1, pairs += 1;
                }
            }
            pairs += rbrac;
            ps[i].lbrac = lbrac;
            ps[i].rbrac = rbrac;
            ps[i].pairs = pairs;
            sumlen += len;
        }
        // We need to arrange them in a timely manner so that
        // there is some part of greedy in it.
        sort(ps + 1, ps + n + 1);
        // To dynamic programming or not, this is a question
        int mx = (sumlen + 1) / 2;
        int now = 1, last = 0;
        dp[now][0] = 0;
        for (int j = 1; j <= mx; j++)
            dp[now][j] = -infinit;
        swap(now, last);
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= mx; j++)
                dp[now][j] = dp[last][j];
            int lbrac = ps[i].lbrac,
                rbrac = ps[i].rbrac,
                pairs = ps[i].pairs;
            for (int j = rbrac; j + lbrac - rbrac <= mx && j <= mx; j++) {
                maximize(dp[now][j + lbrac - rbrac], dp[last][j] + pairs);
            }
            swap(now, last);
        }
        // Now getting result.
        int res = dp[last][0] * 2;
        printf("%d\n", res);
    }
    return 0;
}