P1241 括号序列

题目描述

定义如下规则序列(字符串)：

1．空序列是规则序列；

2．如果S是规则序列，那么(S)和[S]也是规则序列；

3．如果A和B都是规则序列，那么AB也是规则序列。

例如，下面的字符串都是规则序列：

()，[]，(())，([])，()[]，()[()]

而以下几个则不是：

(，[，]，)(，())，([()

现在，给你一些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对于序列a1，a2，…，an和序列bl，b2，…，bm，如果存在一组下标1≤i1<i2<…<in≤m，使得aj＝b(i,j)对一切1≤j≤n成立，那么a1，a2…，an就叫做b1，b2，…，bm的子列。

输入输出格式

输入格式：

 

输入文件仅一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，长度不超过100。

 

输出格式：

 

输出文件也仅有一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。

 

输入输出样例

输入样例#1：

([()

输出样例#1：

()[]()

说明

输出解释：

{最多的嵌套层数为1，如层数为2时的一种为()[()]}

jsoi2011

 

/*69分 维护栈*/#include
         
          #include
          
           #include
           
            using namespace std;const int MAXN=120;const int INF=0x7fffffff;int f[MAXN][MAXN],a[MAXN][MAXN];char s[MAXN];int n;void aaaa(int x,int y){    if (x>y)        return;    if (x==y)    {        if (s[x]=='('||s[x]==')')            printf("()");        else              printf("[]");    }        else    {        if (a[x][y]==-1)        {            if(s[x]=='(')            {                printf("(");                aaaa(x+1,y-1);                printf(")");            }                else            {                printf("[");                aaaa(x+1,y-1);                printf("]");            }            }         else        {            aaaa(x,a[x][y]);            aaaa(a[x][y]+1,y);        }           }    }       int main(){  // gets(s);     scanf("%s",&s);     n=strlen(s);    memset(f,0,sizeof(f));    for (int i=n;i>0;i--)    {        s[i]=s[i-1];        f[i][i]=1;    }        int tot;    for (int p=1;p<=n;p++)    {        for (int i=1;i<=n-p;i++)        {            int j=i+p;            f[i][j]=INF;            if ((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']'))            {                tot=f[i+1][j-1];                if (f[i][j]>tot)                   f[i][j]=tot;            }                a[i][j]=-1;            for (int k=i;k
            
             tot)                {                    f[i][j]=tot;                    a[i][j]=k;                }                }            }        }      aaaa(1,n);    return 0;}