Brackets Sequence（升级版）

个人心得：又是途径问题，我怕是又炸了。看了题解他的意思就是找出最短的添加顺序的断点，则只要

根据断点添加就好了，注意递归的奥妙之处吧，暂时还真得是拿他没办法。

题目描述：

定义合法的括号序列如下：

1 空序列是一个合法的序列

2 如果S是合法的序列，则(S)和[S]也是合法的序列

3 如果A和B是合法的序列，则AB也是合法的序列

例如：下面的都是合法的括号序列

(), [], (()), ([]), ()[], ()[()]

下面的都是非法的括号序列

(, [, ), )(, ([)], ([(]

给定一个由'(', ')', '[', 和 ']' 组成的序列，找出以该序列为子序列的最短合法序列。

Sample Input

([(]

Sample Output

()[()]

解题思路：

根据“黑书”的思路，定义：

d[i][j]为输入序列从下标i到下标j最少需要加多少括号才能成为合法序列。0<=i<=j<len (len为输入序列的长度)。

c[i][j]为输入序列从下标i到下标j的断开位置，如果没有断开则为-1。

当i==j时，d[i][j]为1

当s[i]=='(' && s[j]==')' 或者 s[i]=='[' && s[j]==']'时，d[i][j]=d[i+1][j-1]

否则d[i][j]=min{d[i][k]+d[k+1][j]} i<=k<j ， c[i][j]记录断开的位置k

采用递推方式计算d[i][j]

输出结果时采用递归方式输出print(0, len-1)

输出函数定义为print(int i, int j)，表示输出从下标i到下标j的合法序列

当i>j时，直接返回，不需要输出

当i==j时，d[i][j]为1，至少要加一个括号，如果s[i]为'(' 或者')'，输出"()"，否则输出"[]"

当i>j时，如果c[i][j]>=0，说明从i到j断开了，则递归调用print(i, c[i][j]);和print(c[i][j]+1, j);

如果c[i][j]<0，说明没有断开，如果s[i]=='(' 则输出'('、 print(i+1, j-1); 和")"

否则输出"[" print(i+1, j-1);和"]"

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iomanip>

#include<string>

#include<algorithm>

using namespace std;

int d[][];

int c[][];

string ch;

const int inf=;

int check(int i,int j);

void dp(){

   int i,j,k,l;

   int mina;

   for(i=;i<ch.size();i++)

      d[i][i]=;

   for(l=;l<ch.size();l++)

   {

       for(i=;i+l<ch.size();i++){

                j=l+i;

                mina=d[i][i]+d[i+][j];

                c[i][j]=i;

                for(k=i+;k<j;k++)

                    {

                        if(d[i][k]+d[k+][j]<mina)

                        {

                            mina=d[i][k]+d[k+][j];

                            c[i][j]=k;

                        }

                    }

                    d[i][j]=mina;

                    if(check(i,j)&&d[i+][j-]<mina){

                        d[i][j]=d[i+][j-];

                        c[i][j]=-;

                    }

          }

   }

}

void print(int i,int j){

    if(i>j) return ;

    if(i==j)

    {

        if(ch[i]=='('||ch[i]==')')

            cout<<"()";

        else

            cout<<"[]";

    }

    else

    {

        if(c[i][j]>=)

        {

            print(i,c[i][j]);

            print(c[i][j]+,j);

        }

        else

        {

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

            {

                cout<<"(";

                print(i+,j-);

                cout<<")";

            }

            else

            {

                cout<<"[";

                print(i+,j-);

                cout<<"]";

            }

        }

    }

}

int check(int i,int j){

    if((ch[i]=='('&&ch[j]==')')||(ch[i]=='['&&ch[j]==']'))

        return ;

      return ;

}

void init(){

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

     for(int j=;j<ch.size();j++)

        d[i][j]=;

}

int main(){

             cin>>ch;

            dp();

            print(,ch.size()-);

            cout<<endl;

    return ;

}

巴特西

Brackets Sequence（升级版）

最新文章

热门文章