CH1801( 括号画家)

Love The Way You Lie 2021-11-01 11:22 258阅读 0赞

题目链接:[https://www.acwing.com/problem/content/152/][https_www.acwing.com_problem_content_152]

达达是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。

这一天，刚刚起床的达达画了一排括号序列，其中包含小括号( )、中括号\[ \]和大括号\{ \}，总长度为N。

这排随意绘制的括号序列显得杂乱无章，于是达达定义了什么样的括号序列是美观的：

(1) 空的括号序列是美观的；

(2) 若括号序列A是美观的，则括号序列 (A)、\[A\]、\{A\} 也是美观的；

(3) 若括号序列A、B都是美观的，则括号序列AB也是美观的。

例如 `[(){}]()` 是美观的括号序列，而`)({)[}](` 则不是。

现在达达想在她绘制的括号序列中，找出其中连续的一段，满足这段子序列是美观的，并且长度尽量大。

你能帮帮她吗？

#### 输入格式 ####

输入一行由括号组成的字符串。

#### 输出格式 ####

输出一个整数，表示最长的美观的子段的长度。

#### 数据范围 ####

字符串长度不超过100000。

#### 输入样例： ####

({({(({()}})}{())})})[){
             {
             {([)()((()]]}])[{)]}{[}{)

#### 输出样例： ####

思路：刚开始以为是个很简单的栈模拟，后来教了一发才发现少考虑了要连续，比如这组样例： ()()(((() 应该是输出4，想了好一会都没思路怎么考虑这种情况。

去找博客看，结果连续找到3篇和我刚开始的思路一样的错误博客（我此时心中充满着疑问，TA们是怎么过的），最后还是找到了正确的博客，

这是某位大佬的博客链接： [https://blog.csdn.net/a\_bright\_ch/article/details/81630322][https_blog.csdn.net_a_bright_ch_article_details_81630322]

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<cstdio>
    #include<queue>
    using namespace std;
    char a[200005],b[200005];
    int c[200005];
    int main()
    {
        while(gets(a)!=NULL)
        {
            memset(c,0,sizeof(c));
            int n=strlen(a);
            int k=0,ma=0;
            for(int i=0; i<n; i++)
            {
                if(a[i]=='('||a[i]=='['||a[i]=='{')
                    b[++k]=a[i];
                else if(k>0)
                {
                    if(a[i]==b[k]+1||a[i]==b[k]+2)
                    {
                        c[k]+=1;
                        c[k-1]+=c[k];//理解这就可以了
                        c[k]=0;
                        k--;
                        ma=max(ma,c[k]);
                    }
                    else
                    {
                        while(1)
                        {
                            ma=max(ma,c[k]);
                            c[k]=0;
                            if(k==0)
                                break;
                            k--;
                        }
                    }
                }
            }
            printf("%d\n",2*ma);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/zcb123456789/p/11305629.html

[https_www.acwing.com_problem_content_152]: https://www.acwing.com/problem/content/152/
[https_blog.csdn.net_a_bright_ch_article_details_81630322]: https://blog.csdn.net/a_bright_ch/article/details/81630322