题意：用最少的括号将给定的字符串匹配，输出最优解。可能有空行。
思路：dp。
dp[i][j]表示将区间i，j之间的字符串匹配需要的最少括号数，那么
如果区间左边是(或[，表示可以和右边的字符串匹配，枚举中间断点k，如果str[i]==str[k]则dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k+1][j])表示不需要加入新的括号，也可以插入新的括号则dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+1)。
如果区间最左边字符是）或]，那么它不可能和右边字符串匹配，状态转移为dp[i][j]=min(dp[i][j],dp[i+1][j]+1)
每次转移的时候记录一下转移路径，最后dfs输出即可。
注意可能有空串，所以要用gets。但是在题中每行读入之间有空行，所以要多用一个gets来吃掉这个空行，否则会出错。
建议交UVa，数据比较强。POJ和ZOJ数据较弱，我最初的代码在POJ和ZOJ都过了，UVa却一直TLE。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
#define INF 10000000
#define LL long long
using namespace std;
][];
][];
][];
][];
];
int dp(int L,int R)
{
;
if(vis[L][R]) return f[L][R];
vis[L][R]=true;
f[L][R]=INF;
if(str[L]=='('||str[L]=='[')
{
for(int i=L; i<=R; ++i)
{
if((str[L]=='('&&str[i]==')')||(str[L]=='['&&str[i]==']'))
{
,i-),sy=dp(i+,R);
if(f[L][R]>sx+sy)
{
f[L][R]=sx+sy;
flag[L][R]=-;
pos[L][R]=i;
}
}
,i),dy=dp(i+,R);
)
{
f[L][R]=dx+dy+;
flag[L][R]=;
pos[L][R]=i;
}
}
}
else
{
,R);
)
{
f[L][R]=sx+;
flag[L][R]=;
pos[L][R]=L;
}
}
return f[L][R];
}
void output(int L,int R)
{
if(L<=R)
{
int p=pos[L][R];
)
{
putchar(str[L]);
output(L+,p-);
putchar(str[p]);
output(p+,R);
}
else
{
if(str[L]==')'||str[L]==']')
{
if(str[L]==')') putchar('(');
else putchar('[');
putchar(str[L]);
output(L+,R);
}
else
{
putchar(str[L]);
output(L+,p);
if(str[L]=='(') putchar(')');
else putchar(']');
output(p+,R);
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
getchar();
while(T--)
{
gets(str);
gets(str);
memset(vis,,sizeof(vis));
int L=strlen(str);
dp(,L-);
output(,L-);
putchar('\n');
if(T) putchar('\n');
}
;
}