浙江财经大学
信息管理与工程学院

POJ 2955 Brackets

本文由 Ocrosoft 于 2016-08-20 22:27:58 发表
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 6396 Accepted: 3425

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 a1a2 … 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 i1i2, …,im where 1 ≤ i1 < i2 < … < im ≤ nai1ai2 … 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

题意:给出一个串,里面有'(‘,’)’,'[‘,’]’四种括号,求最大匹配括号数量(不是对数,要乘2)。
思路:区间DP入门题,模板…
dp[i][j]记为i到j的最大匹配数量,
在已知i到j的最大匹配的情况下,如果i-1和j+1是匹配的,那么dp[i-1][j+1]=dp[i][j]+2,是新的最大匹配。
更新最大值,枚举中间值f,dp[i][j]=max(dp[i][f],dp[i][f]+dp[f+1][j])。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const int INF = INT_MAX;
const int MAXN = 100 + 10;
using namespace std;
int dp[MAXN][MAXN];
int main()
{
	char s[MAXN];
	while (cin >> s)
	{
		if (strcmp(s, "end") == 0)break;
		ms(dp);
		int i, j, k, f, len = strlen(s);
		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]);
			}
		}
		printf("%d\n", dp[0][len - 1]);
	}
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » POJ 2955 Brackets

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址