[POJ2955] Brackets

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld

题目描述

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:

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

while the following character sequences are not:

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

Given a brackets sequence of characters $a_1,a_2,\dots, 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_1, i_2,\dots,i_m$ where $1 ≤ i_1 < i_2 < … < i_m ≤ n, a_{i1}a_{i2} … a_{im}$ is a regular brackets sequence.

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

输入描述:

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.

输出描述:

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

输入

1
2
3
4
5
6
((()))
()()()
([]])
)[)(
([][][)
end

输出

1
2
3
4
5
6
6
4
0
6

题目解析

题解

今天刚学区间dp,在大佬的帮助下,我终于理解了这道区间dp题.这道题说来也简单,但是我卡在某个点处了.

这道题区间dp的原理是将括号分为两部分,分别进行dp匹配:

1
2
3
4
5
6
7
例如一个示例数据:([]])([])
我们可以把某个匹配的括号作为分界线,分别dp匹配括号里面的和匹配括号外面的.
([]])([])
|0  |4
这两个是匹配的,所以我们可以匹配这两个括号里面以及外面的:
dp[0][4] = dp[1][3]+2; dp[0][8] = dp[0][4]+dp[5][8];
由于我们并不知道这个分界点在哪里,所以我们需要枚举在这个范围内所有的数据作为分界点.

也就是状态转移方程:

与此同时,我们需要注意的是:第二个状态转移方程是需要获得区间内所有的值的,也就是:

如果我们从前往后,从大往小dp的话,区间内的sub区间的值我们是不知道的,所以我们需要从小往大dp.也就是从左右界相等的点往大区间这样dp过去.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

string s;
int dp[110][110]{};

void solve(){
    for(int len=1;len<s.size();len++){//dp区间的长度，从1->s.size()
        for(int start=0;start+len<s.size();start++){//起始点的位置,起始点+dp区间的长度不能超过s.size().start+len是终点位置,start是起点位置.
            int end = start + len;//终点位置
            if(s[start] == '(' && s[end] == ')' || s[start] == '[' && s[end] == ']'){
                dp[start][end] = dp[start+1][end-1] + 2;//如果两侧有匹配的,那么这个start->end的dp值即里面的加上外面两个的.
            }
            for(int k=start;k<=end;k++){//当上面没有匹配的时候,并不说明这里面没有匹配的括号.
                dp[start][end] = max(dp[start][end],dp[start][k] + dp[k+1][end]);
            }
        }
    }
    return;
}

int main(){
    while(cin >> s){
        if(s == "end") break;
        memset(dp,0,sizeof(dp));
        solve();
        cout << dp[0][s.size()-1] << endl;
    }
    return 0;
}