首页 > ACM题库 > 九度OJ > 九度-1342-寻找最长合法括号序列II(25分)[解题代码]
2013
12-13

九度-1342-寻找最长合法括号序列II(25分)[解题代码]

题目描述:
假如给你一个由’(‘和’)’组成的一个随机的括号序列,当然,这个括号序列肯定不能保证是左右括号匹配的,所以给你的任务便是去掉其中的一些括号,使得剩下的括号序列能够左右括号匹配且长度最长,即最长的合法括号序列。
输入:
测试数据包括多个,每个测试数据只有一行,即一个随机的括号序列,该括号序列的长度保证不超过106
输出:
对于每个测试案例,输出一个整数,表示最后剩下的最长合法括号序列长度。
样例输入:
(())()
(()
样例输出:
6
2

cpp 代码如下:
#include <stdio.h>
char s[1000001];
int i, l, r, ans;
int main(){
	while (scanf("%s",s) != EOF) {
		l = ans = 0;
		for(i=0; s[i]; i++){
			if(s[i] == '('){
				l++;
			}else{
				if(l){
					ans += 2;
					l--;
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

/**************************************************************
	Problem: 1342
	User: coder
	Language: C
	Result: Accepted
	Time:40 ms
	Memory:1892 kb
****************************************************************/


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的