HDU - 6299 Balanced Sequence (2018 Multi-University Training Contest 1 B)

Balanced Sequence
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2043    Accepted Submission(s): 504  
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番目の右側に配置して形成するマッチングシーケンス長です.したがって、左かっこをできるだけ右かっこの左側にするためには、左かっこの数に応じて、大きいものから小さいものまで並べ替えた欲張り処理をすればよい(右かっこでもよい)
 

#include 
using namespace std;
const int MAXN=100505;
typedef long long int ll;

pair li[MAXN];
bool cmp(pair &a,pair &b){
    return a.first>b.first;
}

char str[MAXN];
int main()
{
    int T;
    scanf("%d",&T);
    for(int qqq=0;qqqrn){
                ans+=ln;
                l-=ln;
                li[i].second-=ln;
            }
            else{
                ans+=rn;
                r-=rn;
                li[i].first-=rn;
            }
            l+=li[i].first;
            r+=li[i].second;
        }
        printf("%d
",ans*2);
    }
    return 0;
}