首页 » 未分类 » 正文

2018 Multi-University Training Contest 1 Balanced Sequence(括号匹配)


来源:http://acm.hdu.edu.cn/showproblem.php?pid=6299

Problem Description

Chiaki has n strings s1,s2,…,sn consisting of ‘(‘ and ‘)’. A string of this type is said to be balanced:
+ if it is the empty string
+ if A and B are balanced, AB is balanced,
+ if A is balanced, (A) is balanced.
Chiaki can reorder the strings and then concatenate them get a new string t. Let f(t) be the length of the longest balanced subsequence (not necessary continuous) of t. Chiaki would like to know the maximum value of f(t) for all possible t.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1≤n≤105) — the number of strings.
Each of the next n lines contains a string si (1≤|si|≤105) consisting of (' and)’.
It is guaranteed that the sum of all |si| does not exceeds 5×106.

Output

For each test case, output an integer denoting the answer.

Sample Input

2
1
)()(()(
2
)
)(

Sample Output

4
2

Source

2018 Multi-University Training Contest 1

Recommend

liuyiding

总结

首先算出每个串中已经匹配的个数,然后记录其中没有匹配的左括号和右括号个数。根据未匹配的括号个数进行排序。排序规则如下:
1. 两个串的左括号都大于右括号,将右括号多的放到后面,匹配的个数为大的未匹配右括号个数和小的未匹配左括号个数的最小值。
2. 两个串的右括号都大于左括号,将左括号多的放到前面,匹配的个数为大的未匹配左括号个数和小的未匹配右括号个数的最小值。
3. 一个右括号多,一个左括号多,将左括号多的放到前面,匹配的个数是右括号多于左括号的右括号个数 与 左括号多于右括号的左括号个数的最小值。

代码

#include<bits/stdc++.h>
#define MAXN 110000
#define ll long long 
using namespace std;  
ll dp[MAXN][2];  //0是左括号个数,1是右括号个数 
int cmp(int a, int b){
    int data_a = dp[a][0]-dp[a][1];  //左括号减去右括号个数 
    int data_b = dp[b][0]-dp[b][1];  
    if(data_a > 0){
        if(data_b > 0) return dp[a][1] < dp[b][1];  //如果两个都左括号大于右括号,则右括号多的放后面 
        else return true;  //一个左括号多,一个右括号多,左括号多的放前面匹配右括号多的 
    } else {
        if(data_b > 0) return false;  //同前面一个左括号多,一个右括号多 
        else return dp[a][0] > dp[b][0];  //两个都右括号多,那么左括号多的放前面去匹配,匹配的是大的左括号数 
    }
}

int main(){
    //freopen("2.txt", "r", stdin);  
    int T;  
    char str[MAXN];  
    scanf("%d", &T);  
    int arr[MAXN];  
    while(T--){
        memset(dp,0,sizeof(dp));  
        int n; 
        scanf("%d", &n);  
        ll ans =0ll;   
        for(int i=1;i<=n;i++) arr[i]=i;  //记录排序后的当前是哪个括号串 
        for(int i=1;i<=n;i++){
            scanf("%s",str);  
            //printf("%s\n",str);  
            int length = strlen(str);  
            for(int j=0;j<length;j++){
                if(str[j] == '('){
                    dp[i][0]++;  
                }else {
                    if(dp[i][0] > 0){  //如果前面有左括号,则匹配,答案+2,左括号-1 
                        ans+=2ll;  
                        dp[i][0]--;  
                    }else {
                        dp[i][1]++;  
                    }
                }
            }
        }
        sort(arr+1, arr+n+1,cmp);  ///排序 
        ll num=0;  
        for(int i=1;i<=n;i++){    ///从前面扫过去,一个个的匹配 
            ans += min(num,dp[arr[i]][1])*2ll;  
            num -= min(num,dp[arr[i]][1]);  
            num += dp[arr[i]][0];  
        }
        printf("%lld\n",ans);  
    }
}

本文共 1 个回复

发表评论