POJ 2955 区间dp - c++编程基础

Brackets

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 2446		Accepted: 1258

Description

We give the following inductive definition of a “regular brackets” sequence:

the empty sequence is a regular brackets sequence,if s is a regular brackets sequence, then ( s) and [ s] are regular brackets sequences, andif a and b are regular brackets sequences, then ab is a regular brackets sequence.no other sequence is a regular brackets sequence

For instance, all of the following character sequences are regular brackets sequences:

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

while the following character sequences are not:

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

Given a brackets sequence of characters a₁a₂ … a_n, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i₁, i₂, …, i_m where 1 ≤ i₁ < i₂ < … < i_m ≤ n, a_i1a_i2 … a_im is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

Input

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input

((()))
()()()
([]])
)[)(
([][][)
end

Sample Output

题意：求最长合法括号序列，

两种写法：

/* ***********************************************
Author :rabbit
Created Time :2014/3/10 19:03:58
File Name :A.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; int dp[300][300]; char str[400]; bool match(char a,char b){ if(a=='('&&b==')')return 1; if(a=='['&&b==']')return 1; return 0; } int main(){ while(~scanf("%s",str)&&str[0]!='e'){ int len=strlen(str); memset(dp,0,sizeof(dp)); for(int i=0;i+1
                
                 
 
                 /* ***********************************************
Author :rabbit
Created Time :2014/3/10 19:03:58
File Name :A.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
                  
                   
#include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         #include 
                        
                          #include 
                         
                           #include 
                          
                            #include 
                           
                             #include 
                            
                              #include 
                             
                               #include 
                              
                                #include 
                                using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; int dp[300][300]; char str[400]; int dfs(int l,int r){ int &res=dp[l][r]; if(res!=-1)return res; if(r-l<2)return res=0; for(int i=l+1;i