5C - Longest Regular Bracket Sequence(最长合法括号子串)

原题链接https://codeforces.com/problemset/problem/5/C

这题我没想到怎么做,感觉特殊情况很多,学习的其它大佬的做法。

题意:给你一个括号序列,让你求长度最大的合法括号子串,以及子串的数目。

思路:先从左到右扫描,遇到'('就cnt ++,遇到')'并且cnt > 0,就标记 st[i] = true, 表示该右括号合法,然后cnt --。反之从右到左扫描,找出合法的左括号。最后再扫描一次,找到最大的合法子串。难点就在于,这样贪心分两次扫描左、右括号是否合法。

代码如下

string s; 
int cnt;
bool st[N];

int main()
{
	IOS;
	cin >> s;
	for(int i = 0 ; i < s.size() ; i ++)
	{
		if(s[i] == '(') cnt ++;
		if(s[i] == ')')
		{
			if(cnt) st[i] = true;
			cnt --;
		}
		if(cnt < 0) cnt = 0;
	}
	
	cnt = 0;
	for(int i = s.size() - 1 ; i >= 0 ; i --)
	{
		if(s[i] == ')') cnt ++;
		if(s[i] == '(')
		{
			if(cnt) st[i] = true;
			cnt --;
		}
		if(cnt < 0) cnt = 0;
	}
	
	int res = 0, sum = 0, f = 0;
	for(int i = 0 ; i < s.size() ; i ++)
	{
		if(st[i]) sum ++;
		else
		{
			if(res < sum) res = sum, f = 1;
			else if(res == sum) f ++;
			sum = 0;
		}
	}
	if(res < sum) res = sum, f = 1;
	else if(res == sum) f ++;
	if(!res) f = 1;	
	cout << res << " " << f << endl;
	
	return 0;
}
上一篇:每天一道算法题:括号序列


下一篇:[CD149D] Coloring Brackets(区间dp)