[POJ - 2955] Brackets

发表于 | 更新于 | 分类于 ， ，
本文字数： 9.8k

链接

\(\text{POJ - 2955}\)

题意

  给你包含小括号和中括号括号序列，求最长合法括号子序列的长度。合法的括号序列满足如下条件：

  1. 空的括号序列是合法的；
  2. 如果一个括号序列\(s\)是合法的，那么\((s)、[s]\)也都是合法；
  3. 如果\(a、b\)是合法的，那么\(ab\)也是合法的；
  4. 其他括号序列都是不合法的；

  括号序列长度\(\text N\)，\(1\leq \text{N}\leq100\)。

分析

  这是一道区间\(\text{DP}\)题目，对于某个序列，如\([xxx]oooo\)，它被分成两部分，\(xxx\)和\(oooo\)；

  设\(dp[i][j]\)表示\([i,j]\)之间的最长合法括号子序列的长度，那么如果\([i+1,j]\)内没有与\(i\)匹配的括号，则\(dp[i][j]=dp[i+1][j]\)，若存在一个\(k\)与之匹配，那么\(dp[i][j]=\max\{dp[i+1][j],dp[i+1][k-1]+dp[k+1][j]+2\}\)(\(i\)与\(k\)匹配)，区间长度从小到大枚举，最终\(dp[1][\text{N}]\)即是答案。

代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
#define MOD 99991

typedef long long ll;

namespace fastIO {
	//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
	//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
	inline int read() {
		char c = getchar(); int x = 0, f = 1;
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
		return x * f;
	}
}

using namespace fastIO;
using namespace std;

string s;
int dp[130][130];
int main() {
	while (cin >> s && s != "end") {
		int n = s.size();
		memset(dp, 0, sizeof(dp));
		for (int len = 2; len <= n ;len++)
			for (int i = 1; i + len - 1 <= n; i++) {
				int j = i + len - 1;
				dp[i][j] = dp[i + 1][j];
				for (int k = i + 1; k <= j; k++)
					if ((s[i - 1] == '(' && s[k - 1] ==')') || (s[i - 1] == '[' && s[k - 1] == ']'))
						dp[i][j] = max(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j] + 2);
			}
		cout << dp[1][n] << endl;
	}
}