C - Longest Regular Bracket Sequence

一道题看这么久，，一直错在第十五个样例，无语。。。。

1.题目：

NEFU要崛起——第4场
3:00:00
OverviewProblemStatusRankDiscussABCDE
C - Longest Regular Bracket Sequence
Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u
SubmitStatusPracticeCodeForces 5C
Description
This is yet another problem dealing with regular bracket sequences.We should remind you that a bracket sequence is called regular, if by inserting ?+? and ?1? into it we can get a correct mathematical expression. For example, sequences ?(())()?, ?()? and ?(()(()))? are regular, while ?)(?, ?(()? and ?(()))(? are not.You are given a string of ?(? and ?)? characters. You are to find its longest substring that is a regular bracket sequence. You are to find the number of such substrings as well.Input
The first line of the input file contains a non-empty string, consisting of ?(? and ?)? characters. Its length does not exceed 106.Output
Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing "0 1".Sample Input
Input
)((())))(()())
Output
6 2
Input
))(
Output
0 1
FAQ | About Virtual Judge | Forum | Discuss | Open Source Project
All Copyright Reserved ?2010-2012 HUST ACM/ICPC TEAM 
Anything about the OJ, please ask in the forum, or contact author:Isun
Server Time: 

2.题意：

给定字符串，判断括号是不是合法

3.一直错在第十五个样例的代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[100000];
int b[100000];
int cmp(int d,int c)
{return d>c;
}int main()
{scanf("%s",a);int count=1;int ans1=0;int ans2=0;int j=0,i;for(int k=0; k<strlen(a); k++){for( i=k; i<strlen(a); i++){if((ans1>=ans2)||(ans1==0&&ans2==0)){if(a[i]=='(')ans1++;if(a[i]==')')ans2++;//printf("ans:%d %d\n",ans1,ans2);}if((ans1==ans2)&&ans1!=0){b[j++]=ans1+ans2;}if(ans1<ans2){ans1=0;ans2=0;k=i;break;}}if(i==strlen(a)){ans1=0;ans2=0;}}sort(b,b+j,cmp);for(int i=0; i<=j; i++){if(b[i]==b[i+1])count++;elsebreak;}if(b[0]!=0)printf("%d %d\n",b[0],count);else printf("0 1\n");return 0;
}

4.徐ac代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int ans,key,dp[1000012];
char s[1000012];
int main()
{while(scanf("%s",&s)!=EOF){int i,j,len=strlen(s);dp[0]=0;ans=0,key=1;for(i=1; i<len; i++){dp[i]=0;if(i-dp[i-1]-1>=0&&s[i]==')'&&s[i-dp[i-1]-1]=='('){dp[i]=dp[i-1]+2;if(i-dp[i-1]-2>=0&&dp[i-dp[i-1]-2]){dp[i]+=dp[i-dp[i-1]-2];}}if(ans<dp[i]) ans=dp[i],key=1;else if(ans==dp[i]&&ans) key++;}cout<<ans<<" "<<key<<endl;}return 0;
}