题意：给你一个括号序列，问你匹配的最长字串长度和个数。
解题思路：栈模拟+ dp
解题代码：
1 // File Name: 5c.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月09日 星期一 12时00分57秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 char str[1000005]; 28 int hs[1000005]; 29 int dp[1000005]; 30 struct node{ 31 int si,val; 32 node(){} 33 node(int _si,int _val) 34 { 35 si = _si ; 36 val =_val; 37 } 38 }; 39 stack <node> st; 40 int main(){ 41 scanf("%s",&str[1]); 42 int len = strlen(&str[1]); 43 int tsum = 0 ; 44 hs[0] = 1; 45 for(int i = 1;i <= len;i ++) 46 { 47 if(str[i] == '(') 48 { 49 st.push(node(i,2)); 50 } 51 else if(str[i] == ')') 52 { 53 if(!st.empty()) 54 { 55 node tmp = st.top(); 56 dp[i] = tmp.val + dp[tmp.si-1]; 57 hs[dp[i]] ++ ; 58 st.pop(); 59 if(!st.empty()) 60 { 61 node k = st.top(); 62 st.pop(); 63 st.push(node(k.si,k.val+tmp.val)); 64 } 65 } 66 } 67 68 } 69 for(int i = 1000000 ;i >= 0 ;i -- ) 70 { 71 if(hs[i]) 72 { 73 printf("%d %d ",i,hs[i]); 74 break; 75 } 76 } 77 return 0; 78 }