UVA1626 - Brackets sequence（区间DP--括号匹配+递归打印）

题目描述：

定义合法的括号序列如下：

1 空序列是一个合法的序列

2 如果S是合法的序列，则(S)和[S]也是合法的序列

3 如果A和B是合法的序列，则AB也是合法的序列

例如：下面的都是合法的括号序列

(), [], (()), ([]), ()[], ()[()]

下面的都是非法的括号序列

(, [, ), )(, ([)], ([(]

给定一个由'(', ')', '[', 和 ']' 组成的序列，找出以该序列为子序列的最短合法序列。

思路：真是经典的题目，区间DP，题目居然有陷阱，输入可能是空串,所以用scanf的时候，会不读入，就少了一次读入，wa

所以用gets

//	Accepted	C++	1.002	2015-03-12 13:34:47
#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; const int inf= 0x3f3f3f3f; int dp[105][105]; char str[105]; int n; bool match(char a,char b) { if(a=='('&&b==')') return true; else if(a=='[' && b==']') return true; return false; } void print(int l,int r) //递归打印解 { if(l>r) return ; if(l==r) { if(str[l]=='('||str[l]==')') printf("()"); else if(str[l]=='['||str[l]==']') printf("[]"); return ; } if(match(str[l],str[r])&&dp[l][r]==dp[l+1][r-1]) //别忘了match(str[l],str[r])，因为dp[l][r]==dp[l+1][r-1]时候，不一定外侧括号匹配，很容易错 { putchar(str[l]); print(l+1,r-1); putchar(str[r]); return ; } for(int k=l;k