poj 1141 Brackets Sequence 区间dp入门

Brackets Sequence

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 29357		Accepted: 8351		Special Judge

Description

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 a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.

Input

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

Output

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

([(]

Sample Output

()[()]

Source

Northeastern Europe 2001

[Submit]   [Go Back]   [Status]   [Discuss]

dp【i ，j】表示第i到j个要满足题意需要加符号的个数

状态转移方程为 当s【i】与s【j】匹配时 dp【i j】=dp【i+1,j-1】

否则 dp【 i j】=min（dp【i，k】 dp【k+1，j】）i<k<j 合并区间

数据不是多组输出

ACcode：

#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define maxn 111
#define inf 0x3f3f3f
using namespace std;
int dp[maxn][maxn];
int path[maxn][maxn];
char s[maxn];
void print(int st,int ed){
    if(st>ed)return;
    else if(st==ed){
        if(s[st]=='('||s[ed]==')')printf("()");
        else printf("[]");
    }
    else if(path[st][ed]==-1){
        putchar(s[st]);
        print(st+1,ed-1);
        putchar(s[ed]);
    }
    else{
        print(st,path[st][ed]);
        print(path[st][ed]+1,ed);
    }
}
int main(){
    scanf("%s",s+1);
        memset(dp,0,sizeof(dp));
        int len=strlen(s+1);
        for(int i=1;i<=len;++i)dp[i][i]=1;
        for(int l=2;l<=len;++l)
            for(int i=1;i<=len-l+1;++i){
                int j=i+l-1;
                if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']'){
                    dp[i][j]=dp[i+1][j-1];
                    path[i][j]=-1;
                }
                else dp[i][j]=inf;
                for(int k=i;k<=j-1;k++){
                    if(dp[i][j]>dp[i][k]+dp[k+1][j]){
                        dp[i][j]=dp[i][k]+dp[k+1][j];
                        path[i][j]=k;
                    }
                }
            }
        print(1,len);
        putchar('\n');

    return 0;
}