Codeforces Beta Round #5 C. Longest Regular Bracket Sequence 栈/dp

C. Longest Regular Bracket Sequence

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/problemset/problem/5/C

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

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

Sample Output

6 2

HINT

题意

给你一个括号序列，让你找到最长的连续的合法括号序列

然后让你输出这个括号序列的长度是多少

这么长的括号序列一共有多少个

题解：

看到括号匹配，就用stack来弄就好了

然后我们再简单dp一下，表示以这个字符结尾的序列的长度是多少

然后跑一发就好了

代码

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 2000001
#define mod 10007
#define eps 1e-9
int Num;
char CH[20];
//const int inf=0x7fffffff;   //нчоч╢С
const int inf=0x3f3f3f3f;
/*

inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
*/
inline ll read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
//**************************************************************************************

string s;
stack<int> k;
int dp[maxn];
int main()
{
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='(')
            k.push(i);
        else
        {
            if(!k.empty())
            {
                dp[i]=i-k.top()+1;
                if(k.top()>0)
                    dp[i]+=dp[k.top()-1];
                k.pop();
            }
        }
    }
    int ans1=0,ans2=1;
    for(int i=0;i<s.size();i++)
    {
        if(dp[i]>ans1)
        {
            ans1=dp[i];
            ans2=1;
        }
        else if(dp[i]==ans1)
            ans2++;
    }
    if(ans1==0)
        printf("0 1
");
    else
        cout<<ans1<<" "<<ans2<<endl;
}