UVA 1626 括号序列（区间dp）

分析：区间dp，装填方程：dp(i,j)=min(dp(i,k)+dp(k+1,j)) 其中（i<=k<j）  dp(i,j)表示从第i个字符到第j个字符的最小需要添加括号字符的个数，最后递归打印出字符即可。

不知道为什么voj上用gets读取字符串会编译错误，改成fgets就对了。

AC代码：

#include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;const int maxn=100+10;int dp[maxn][maxn];char s[maxn];bool match(int i,int j){	if(s[i]=='(' && s[j]==')')return true;	if(s[i]=='[' && s[j]==']')return true;	return false ; }void PRint(int i,int j){	if(i>j)return ;	if(i==j){		if(s[i]=='(' || s[i]==')')printf("()");		else if(s[i]=='[' || s[j]==']')printf("[]");		return ;	}		if(dp[i][j]==dp[i+1][j-1] && match(i,j)){		printf("%c",s[i]);		print(i+1,j-1);		printf("%c",s[j]);		return ;	}		for(int k=i;k<j;k++){		if(dp[i][j]==dp[i][k]+dp[k+1][j]){			print(i,k);			print(k+1,j);			break;		}	}}int main(){	int T;	scanf("%d",&T);	getchar();  //吃掉换行	while(T--){		getchar();  //吃掉换行	    //gets(s+1);	    fgets(s+1,maxn,stdin);		int l=strlen(s+1);	memset(dp,0,sizeof(dp));	for(int i=1;i<=l;i++)	 dp[i][i]=1;	 	 for(int len=2;len<=l;len++)   //长度 	  for(int i=1;i<=l-len+1;i++){   //起点 	  	int j=i+len-1;   //终点 	  	dp[i][j]=maxn;	  	if(match(i,j))dp[i][j]=dp[i+1][j-1];	  	else dp[i][j]=dp[i][j-1]+1;	  		  	for(int k=i;k<j;k++)	  	dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);	  }	  	  print(1,l);	  printf("/n");	  if(T)printf("/n");//	  printf("%d/n",dp[1][l]);	}	return 0;}