Language:Default

Brackets

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 11260		Accepted: 5968

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₁a₂ … 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₁, i₂, …, i_m where 1 ≤ i₁< i₂ < … < i_m ≤ n, a_i1a_i2 … a_im 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

Source

Stanford Local 2004

具体细节在代码中详细讲解~~

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int dp[105][105];//dp[w][s]表示从w到s的字串中，最大的匹配个数是多少（因为是匹配个数所以后面*2输出）
bool match(char a, char b)//看看能否匹配
{
	if ((a == '('&&b == ')') || (a == '['&&b == ']'))
	{
		return 1;
	}
	return 0;
}
int main()
{
	string m;
	while (cin >> m&&m[0]!='e')
	{
		memset(dp, 0, sizeof(dp));//初始化
		int len = m.length();
		for (int s = 1; s < len; s++)//枚举终点
		{
			for (int w = s - 1; w >= 0; w--)//枚举起点，，这里注意要从小范围到大范围的枚举，保证dp的顺序性
			{
				if (match(m[w], m[s]))//如果最两边的可匹配，那就将dp[w][s]初始化为dp[w+1][s-1]+1;
				{
		                     dp[w][s] = max(dp[w][s],dp[w+1][s-1]+1);
				}
				for(int q=w;q<=s;q++)
                                {
                                     dp[w][s]=max(dp[w][s],dp[w][q]+dp[q][s]);//之后枚举断点，看看整个的最大值和分成部分的相加值的比较更新
                                }
			}
		}
		cout << 2*dp[0][len - 1] << endl;//双倍输出
	}
	return 0;
}

括号匹配

时间限制：1000 ms | 内存限制：65535 KB

难度：6

描述

给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。
如：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的

输入

第一行输入一个正整数N，表示测试数据组数(N<=10)
每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100

输出

对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行

样例输入

[]

([])[]

((]

([)]

样例输出

如果想要之后填的越少，那么只要求出原来的字符串中最大的匹配数就好，然后减掉就是答案，

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int dp[105][105];
bool match(char a, char b)
{
	if ((a == '('&&b == ')') || (a == '['&&b == ']'))
	{
		return 1;
	}
	return 0;
}
int main()
{
	string m;
	int test;
	scanf("%d",&test);
	while (test--)
	{
	    cin>>m;
		memset(dp, 0, sizeof(dp));
		int len = m.length();
		for (int s = 1; s < len; s++)
		{
			for (int w = s - 1; w >= 0; w--)
			{
				if (match(m[w], m[s]))
				{
					dp[w][s] = max(dp[w][s],dp[w+1][s-1]+1);
				}
				for(int q=w;q<=s;q++)
                                {
                                        dp[w][s]=max(dp[w][s],dp[w][q]+dp[q][s]);
                                }
			}
		}
		cout << len-2*dp[0][len - 1] << endl;
	}
	return 0;
}

括号匹配（区间dp）

括号匹配