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[];

//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=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

string s;

stack<int> k;

int dp[maxn];

int main()

{

    cin>>s;

    for(int i=;i<s.size();i++)

    {

        if(s[i]=='(')

            k.push(i);

        else

        {

            if(!k.empty())

            {

                dp[i]=i-k.top()+;

                if(k.top()>)

                    dp[i]+=dp[k.top()-];

                k.pop();

            }

        }

    }

    int ans1=,ans2=;

    for(int i=;i<s.size();i++)

    {

        if(dp[i]>ans1)

        {

            ans1=dp[i];

            ans2=;

        }

        else if(dp[i]==ans1)

            ans2++;

    }

    if(ans1==)

        printf("0 1\n");

    else

        cout<<ans1<<" "<<ans2<<endl;

}