首页 > 其他 > 详细

【51NOD 1478】括号序列的最长合法子段

时间:2016-04-26 15:43:18      阅读:241      评论:0      收藏:0      [点我收藏+]

很恶心啊,一道水题改了半天,主要是各种细节没有注意到,包括左括号剩余时有可能会出错的情况,需要从后往前扫

贡献一组测试数据:

((()))())(())((

答案:8 1

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1E6 + 3;
char s[N];
int main() {
	scanf("%s", s);
	int n = strlen(s), now = 0, ans = 0, ans2, sum = 0, top = 0, tmp = 0;
	for(int i = 0; i < n; ++i)
		if (s[i] == ‘(‘)
			++top;
		else {
			if (top) {
				--top;
				sum += 2;
			} else {
				if (sum > now) {
					now = sum; ans = 1;
				} else
					if (sum == now)
						++ans;
				tmp = i + 1;
				top = 0;
				sum = 0;
			}
		}
	
	if (top) {
		ans2 = 0; sum = 0; top = 0;
		for(int i = n - 1; i >= tmp; --i)
			if (s[i] == ‘)‘)
				++top;
			else {
				if (top) {
					--top;
					sum += 2;
				} else {
					if (sum > now) {
						now = sum; ans = 1;
					} else
						if (sum == now)
							++ans;
					top = 0;
					sum = 0;
				}
			}
		if (sum > now)
			now = sum, ans = 1;
		else
			if (sum == now)
				++ans;
	} else {
		if (sum > now)
			now = sum, ans = 1;
		else
			if (sum == now)
				++ans;
	}
	
	if (now == 0)
		ans = 1;
	printf("%d %d\n", now, ans);
	return 0;
}

 

【51NOD 1478】括号序列的最长合法子段

原文:http://www.cnblogs.com/abclzr/p/5435178.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!