括号序列

暴力做法，利用 dfs，能过<40%，need 用来找到最小需要的括号数，dfs中的 left 代表未匹配的左括号，左右括号做法相反。

#include<bits/stdc++.h>
using namespace std;
string s;
int ans,ans2,len,min_size = 0x3f3f3f3f,min_size2=0x3f3f3f3f;
void dfs(int dep,string new_s,int total,int left){if(dep==len){if(new_s.size()==min_size)ans++;else if(new_s.size()<min_size){min_size = new_s.size();ans = 1;}return;}if(s[dep]=='(')dfs(dep+1,new_s+"(",total,left+1);else{int st = 0;if(left==0)st = 1;for(int i=st;i<=total;i++){string add;for(int j = 1;j<=i;j++){add += '(';}dfs(dep+1 ,new_s+add+")",total-i , left+i-1);}}
}void dfs2(int dep2,string new_s2,int total2,int right){if(dep2==len){if(new_s2.size()==min_size2)ans2++;else if(new_s2.size()<min_size2){min_size2 = new_s2.size();ans2 = 1;}return;}if(s[dep2]==')')dfs2(dep2+1,new_s2+")",total2,right+1);else{int st = 0;if(right==0)st = 1;for(int i=st;i<=total2;i++){string add;for(int j = 1;j<=i;j++){add += ')';}dfs2(dep2+1 ,new_s2+add+"(",total2-i , right+i-1);}}
}int main( ){cin>>s;len = s.size();int need = 0,left = 0;for(int i=0;i<len;i++){if(s[i]=='(')left++;else left--;if(left<0)need++,left=0;}dfs(0,"",need,0);need = 0;int right = 0;for(int i=0;i<len;i++){if(s[i]==')')right++;else right--;if(right<0)need++,right=0;}dfs2(0,"",need,0);cout<<ans*ans2<<endl;return 0;
}