UVA 1626 - Brackets sequence

http://www.cnblogs.com/20143605--pcx/p/4791122.html
Let us define a regular brackets sequence in the following way:

1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. If A and B are regular sequences, then AB is a regular sequence.

For example, all of the following sequences of characters are regular brackets sequences:
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a₁a₂...a_n is called a subsequence of the string b₁b₂...b_m, if there exist such indices 1 ≤ i₁ < i₂ < ... < i_n ≤ m, that a_j=b_ij for all 1 ≤ j ≤ n.

Input 

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.


The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.

Output 

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.


Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.

Sample Input 

1

([(]

Sample Output 

()[()]

这是《入门经典》上的一道例题。如果仅让求最短序列是极简单的，定义dp(i,j)表示将区间 i~j 变为合法添加的最小字符数.

　　　　　　则 dp(i,j)=dp(i+1,j-1)   （i与j能匹配时)，　　　　dp(i,j)=min(dp(i,k)+dp(k+1,j))。

但是，输出的时候就比较慢了。从左往右通过比较选择最优方案递归输出（看的书上代码）。

char p[105];

int dp[105][105];

const int INF=100000;

bool match(int x,int y)

{

    if(p[x]=='('&&p[y]==')')

        return true;

    if(p[x]=='['&&p[y]==']')

        return true;

    return false;

}

void DP()

{

    int len=strlen(p);

    for(int l=1;l<=len;++l){

        for(int i=0;i+l-1<len;++i){

            int r=i+l-1;

            if(l==1){

                dp[i][r]=1;

                continue;

            }

            if(l==2){

                if(match(i,r))

                    dp[i][r]=0;

                else

                    dp[i][r]=2;

                continue;

            }

            dp[i][r]=INF;

            if(match(i,r))

                dp[i][r]=dp[i+1][r-1];

            for(int k=i;k<r;++k){

                dp[i][r]=min(dp[i][r],dp[i][k]+dp[k+1][r]);

            }

        }

    }

}

void print(int i,int j)

{

    if(i>j)

        return ;

    if(i==j){

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

            printf("()");

        else

            printf("[]");

        return ;

    }

    int ans=dp[i][j];

    if(match(i,j)&&ans==dp[i+1][j-1]){

        printf("%c",p[i]);

        print(i+1,j-1);

        printf("%c",p[j]);

        return ;

    }

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

        if(ans==dp[i][k]+dp[k+1][j]){

            print(i,k);

            print(k+1,j);

            return ;

        }

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    getchar();

    while(T--)

    {

        getchar();

        gets(p);

        int len=strlen(p);

        if(len>0){

            DP();

            print(0,len-1);

        }

        printf("\n");

        if(T)

            printf("\n");

    }

    return 0;

}