贪心+stack Codeforces Beta Round #5 C. Longest Regular Bracket Sequence

题目传送门

 /*
     题意：求最长括号匹配的长度和它的个数
     贪心+stack：用栈存放最近的左括号的位置，若是有右括号匹配，则记录它们的长度，更新最大值，可以在O (n)解决
     详细解释：http://blog.****.net/taoxin52/article/details/26012167
 */
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <cmath>
 #include <stack>
 using namespace std;

 const int MAXN = 1e6 + ;
 const int INF = 0x3f3f3f3f;
 char s[MAXN];
 int len[MAXN];
 stack<int> S;

 int main(void)        //Codeforces Beta Round #5 C. Longest Regular Bracket Sequence
 {
 //    freopen ("C.in", "r", stdin);

     while (scanf ("%s", s) == )
     {
         while (!S.empty ())    S.pop ();
         memset (len, , sizeof (len));

         int mx = ;    int cnt = ;
         for (int i=; s[i]; ++i)
         {
             if (s[i] == '(')    S.push (i);
             else
             {
                 if (!S.empty ())
                 {
                     int p = S.top ();    S.pop ();
                     len[i] = (p >  ? len[p-] : ) + (i - p + );
                 }
             }
             if (len[i] > mx)    {mx = len[i];    cnt = ;}
             else if (len[i] == mx)    {cnt++;}
         }

         if (mx == )    puts ("0 1");
         else    printf ("%d %d\n", mx, cnt);
     }

     return ;
 }