E - Longest Regular Bracket Sequence CodeForces - 5C DP+栈

柔光的暖阳◎ 2021-09-20 12:06 266阅读 0赞

[**E - Longest Regular Bracket Sequence**][E - Longest Regular Bracket Sequence] [CodeForces - 5C ][CodeForces - 5C]

> 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".
> 
> Examples
> 
> **Input**
> 
>     )((())))(()())
> 
> **Output**
> 
>     6 2
> 
> **Input**
> 
>     ))(
> 
> **Output**
> 
>     0 1

题意：寻找最长的满足括号匹配规则的字串（括号匹配规则就平时生活中用的那样）

思路：dp\[i\]存以str\[i\]为终点的最长满足条件的字符串长度，

括号匹配很容易想到栈wz：遇到“（”就把下标入栈，遇到“）”就更新dp：1. dp\[i\] = i - wz.top +1;(wz.top与i之间的字符是能匹配才会出栈，所以此时长度就是i - wz.top +1)2.因为会有（）（）（（（））（））的情况，如果只用上面的式子的话就会漏掉前面的（）（），所以 dp\[i\] + = dp \[ wz.top-1 \];

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <queue>
    #include <map>
    #include <set>
    #include <stack>
    #define fora(i,a,b) for(i=a;i<b;i++)
    #define fors(i,a,b) for(i=a;i>b;i--)
    #define fora2(i,a,b) for(i=a;i<=b;i++)
    #define fors2(i,a,b) for(i=a;i>=b;i--)
    #define PI acos(-1.0)
    #define eps 1e-6
    #define INF 0x3f3f3f3f
    
    typedef long long LL;
    typedef long long LD;
    using namespace std;
    const int maxn=1e6+11;
    const int mod=10056;
    
    char str[maxn];
    stack<int>wz;
    int dp[maxn];
    int main()
    {
        while(~scanf("%s",str))
        {
            while(!wz.empty())wz.pop();
            memset(dp,0,sizeof(dp));
            int ans=0,ansc=1;
            int len=strlen(str);
            for(int i=0;i<len;i++)
            {
                if(str[i]=='(')wz.push(i);
                else
                {
                    if(wz.empty())
                    {
                        continue;
                    }
                    int t=wz.top();
                    wz.pop();
                    dp[i]=i-t+1;
                    if(t>0)
                        dp[i]+=dp[t-1];
                    if(ans==dp[i])ansc++;
                    if(ans<dp[i])
                    {
                        ans=dp[i];
                        ansc=1;
                    }
                }
            }
            if(ans==0)ansc=1;
            printf("%d %d\n",ans,ansc);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/107acm/p/9428311.html

[E - Longest Regular Bracket Sequence]: https://vjudge.net/problem/CodeForces-5C
[CodeForces - 5C]: https://vjudge.net/problem/19990/origin