题意：
给你一个括号序列（有中小括号），求出以给定序列为子序列的最小合法括号序列。
分析：
非常经典，以前做过相似一道题，用区间dp，但怎么把这个序列求出来没想出来。
dp[i][j]表示区间i-j是序列合法要增加括号的最小数量，并pos[i][j]表示i-j在哪个位置断开最小，最后通过递归位置打印出答案。
此题序列可能是空串。
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = ;
int dp[][],pos[][],len;
char s[];
void solve(){
memset(dp,,sizeof(dp));
for(int i=;i<len;++i)
dp[i][i]=;
for(int l=;l<len;++l)
for(int i=;i+l<len;++i){
int j=i+l;
int minv=INF;
for(int k=i;k<j;++k){
if(dp[i][k]+dp[k+][j]<minv)
{
minv=dp[i][k]+dp[k+][j];
pos[i][j]=k;
}
}
if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']'){
if(dp[i+][j-]<minv){
minv=dp[i+][j-];
pos[i][j]=-;
}
}
dp[i][j]=minv;
}
}
void dfs(int l,int r){
if(l>r)return;
if(l==r){
if(s[l]=='('||s[l]==')')
printf("()");
else printf("[]");
}
else{
if(pos[l][r]>=){
dfs(l,pos[l][r]);
dfs(pos[l][r]+,r);
}
else{
if(s[l]=='('){
printf("(");
dfs(l+,r-);
printf(")");
}
else{
printf("[");
dfs(l+,r-);
printf("]");
}
}
}
}
int main()
{
int ca=,t;
scanf("%d",&t);
getchar();
while(t--){
gets(s);
gets(s);
memset(pos,-,sizeof(pos));
len=strlen(s);
if(len==)
{
printf("\n");
if(t)printf("\n");
continue;
}
solve();
dfs(,len-);
printf("\n");
if(t)printf("\n");
}
return ;
}