首页 > itarticle > [poj

[poj

admin 11月 14, 2020 0

链接

(text{POJ - 2955})

题意

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

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

括号序列长度(text N)，(1leq 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}])即是答案。

代码


#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 {
	
	//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
	inline int () {
		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;
	}
}