POJ 2955-Brackets（括号匹配-区间DP）

短命女 2022-08-22 12:30 154阅读 0赞

# Brackets #

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 5484</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 2946</td> 
  </tr> 
 </tbody> 
</table>

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, and
 *  if *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*1*a*2 … *an*, 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*1, *i*2, …, *im* where 1 ≤ *i*1 < *i*2 < … < *im* ≤  *n*, *ai*1*ai*2 … *aim* 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

6
    6
    4
    0
    6

Source

[Stanford Local 2004][]

## 题目意思： ##

最大括号匹配数。

## 解题思路： ##

[From][]

定义dp \[ i \] \[ j \] 为串中第 i 个到第 j 个括号的最大匹配数目

那么我们假如知道了 i 到 j 区间的最大匹配，那么i+1到 j+1区间的是不是就可以很简单的得到。

那么 假如第 i 个和第 j 个是一对匹配的括号那么 **dp \[ i \] \[ j \] = dp \[ i+1 \] \[ j-1 \] + 2 ;**

那么我们只需要从小到大枚举所有 i 和 j 中间的括号数目，然后满足匹配就用上面式子dp，然后每次更新dp \[ i \] \[ j \]为最大值即可。

更新最大值的方法是枚举 i 和 j 的中间值，然后让  **dp\[ i \] \[ j \] = max ( dp \[ i \] \[ j \] , dp \[ i \] \[ f \] + dp \[ f+1 \] \[ j \] ) 。**

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<set>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define MAXN 202
    #define INF 999999
    int dp[MAXN][MAXN];
    
    int main()
    {
        string s;
        while(cin>>s)
        {
            if(s=="end")  break;
            memset(dp,0,sizeof(dp));
            int i,j,k,f,len=s.size();
            for(i=1; i<len; i++)
                for(j=0,k=i; k<len; j++,k++)
                {
                    if((s[j]=='('&&s[k]==')')||(s[j]=='['&&s[k]==']'))
                        dp[j][k]=dp[j+1][k-1]+2;
                    for(f=j; f<k; f++)
                        dp[j][k]=max(dp[j][k],dp[j][f]+dp[f+1][k]);
                }
            //len-dp[0][len-1]表示需要补充多少括号才能都匹配成功
            cout<<dp[0][len-1]<<endl;
        }
        return 0;
    }

[Stanford Local 2004]: http://poj.org/searchproblem?field=source&key=Stanford+Local+2004
[From]: http://www.tuicool.com/articles/r2MBJf