Chiaki has nn strings s1,s2,…,sns1,s2,…,sn consisting of '(' and ')'. A string of this type is said to be balanced:
+ if it is the empty string
+ if AA and BB are balanced, ABAB is balanced,
+ if AA is balanced, (A)(A) is balanced.
Chiaki can reorder the strings and then concatenate them get a new string tt. Let f(t)f(t) be the length of the longest balanced subsequence (not necessary continuous) of tt. Chiaki would like to know the maximum value of f(t)f(t) for all possible tt.
Input
There are multiple test cases. The first line of input contains an integer TT, indicating the number of test cases. For each test case:
The first line contains an integer nn (1≤n≤1051≤n≤105) -- the number of strings.
Each of the next nn lines contains a string sisi (1≤|si|≤1051≤|si|≤105) consisting of `(' and `)'.
It is guaranteed that the sum of all |si||si| does not exceeds 5×1065×106.
Output
For each test case, output an integer denoting the answer.
Sample Input
2 1 )()(()( 2 ) )(
Sample Output
4 2
题意：
给的n个字符串排列后并连接，求新得的字符串中最长平衡子序列。
思路：(参考博客)
首先对每个字符串进行处理，将其中的平衡子序列去除，那么处理完后的序列只有三种可能：((、))、))((
将其存入结构体中，之后按照贡献大小来排序，然后从头开始合并。
这道题的难点在于排序。
排序的话遵守一个原则，就是他们自己谁能对形成配对的贡献大，比如说，这个字符串里 '(' 出现的次数比 ')' 那么它就比较适合排左边（前面），反之')'比较多的话适合排在后面，这样能够使自己对整个配对做出的贡献最大，a和b比较的话，如果a和b都是'('贡献大的话谁的')'小就排前面，因为相对来说')'的要往后排，相对贡献会大一些
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
#define mod (1000000007)
using namespace std;
typedef long long ll;
/*贪心 */
struct node{int t1,t2;//t1-'(' t2-')'friend bool operator<(node a,node b){if(a.t2<=a.t1&&b.t2>b.t1)return true;if(a.t2>a.t1&&b.t2<=b.t1)return false;if(a.t1>=a.t2&&b.t1>=b.t2)return a.t2<b.t2; return a.t1>b.t1;}
}s1[100010];
int n;
char ss[100010];
int top=0,cnt=0;
char str[100010];
int main()
{int t;scanf("%d",&t);while(t--){int lf=0,ri=0;//lf-'(' ri=')'cnt=0;int sum=0; int n;scanf("%d",&n);for(int j=0;j<n;j++){top=0;scanf("%s",str);int len=strlen(str);for(int i=0;str[i];i++){//将一个字符串中平衡子序列除掉 (分成两部分一个是去除后是')('这种的，还有就是去除后只剩单个的) if(str[i]=='(')ss[top++]='(';else{if(top>0&&ss[top-1]=='(')top--;elsess[top++]=')';}}sum+=len-top;if(top!=0){if(ss[0]=='(')lf+=top;else if(ss[top-1]==')')ri+=top;else{for(int i=0;i<top;i++){if(ss[i]=='('){s1[cnt].t1=top-i;s1[cnt++].t2=i;break;}}}}}s1[cnt].t1=lf;//将单个的加入到结构体中 s1[cnt++].t2=0;s1[cnt].t1=0;s1[cnt++].t2=ri;sort(s1,s1+cnt);//排序 node tmp;tmp.t1=0;tmp.t2=0;for(int i=0;i<cnt;i++){if(tmp.t1>=s1[i].t2){sum+=s1[i].t2*2;//要乘2 tmp.t1=tmp.t1-s1[i].t2+s1[i].t1;}else{sum+=tmp.t1*2;//要乘2tmp.t2+=s1[i].t2-tmp.t1;tmp.t1=s1[i].t1;}}printf("%d\n",sum);}return 0;
}