uva
紫书例题，这个区间dp最容易错的应该是(S)这种匹配情况，如果不是题目中给了提示我就忽略了，只想着左右分割忘记了这种特殊的例子。
dp[i][j]=MIN{dp[i+1][j-1] | if(match(i,j) , dp[i][k]+dp[k+1][j] | i<=k<=j .}
注意初始化dp[i][i]=1,表示1个字符最少需要一个才能匹配，dp[i+1][i]=0,因为可能只有两个字符使得i+1>j-1,我们可以认为中间是空字符已经匹配了。
打印路径利用了递归，很巧妙，lrj的代码确实短小精悍。
还有就是本题的输入输出要注意，可能出现空串，输入的每一行字符间(包括第一行字符和t之间)都要键入一个空格，输出每两个答案之间输出一个空格。
为了防止getline()将输入的t读入到s中，我们将t以字符形式读入。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int dp[][];
char s[];
bool match(int i,int j)
{
return (s[i]=='['&&s[j]==']')||(s[i]=='('&&s[j]==')');
}
void print(int l,int r)
{
if(l>r) return;
if(l==r){
if(s[l]=='['||s[r]==']') printf("[]");
else printf("()");
return;
}
if(dp[l][r]==dp[l+][r-]&&match(l,r)){
printf("%c",s[l]);
print(l+,r-);
printf("%c",s[r]);
return;
}
for(int k=l;k<=r;++k){
if(dp[l][r]==dp[l][k]+dp[k+][r]){
print(l,k);
print(k+,r);
return;
}
}
}
int main()
{
int t,n,m=,i,j,k;
cin.getline(s,);
t=atoi(s);
while(t--){getchar();m++;
if(m>) puts("");
cin.getline(s+,);
n=strlen(s+);
memset(dp,inf,sizeof(dp));
for(i=;i<=n;++i)
{
dp[i][i]=;
dp[i+][i]=;
}
for(int len=;len<=n;++len)
{
for(i=,j=len;j<=n;++i,++j)
{
if(match(i,j)) dp[i][j]=min(dp[i][j],dp[i+][j-]);
for(k=i;k<=j;++k)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);
}
}
}
//cout<<dp[1][n]<<endl;
print(,n);puts("");
}
return ;
}