首页 > 代码库 > POJ 1141 输出正确的括号匹配(最少添加)

POJ 1141 输出正确的括号匹配(最少添加)

2024-11-02 16:53:38   204人阅读

Brackets Sequence
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 32174 Accepted: 9291 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

()[()]

在上面那个NYoj的基础上添加打印，打印的时候重新检查一下哪个决策最好。好处是节约空间，坏处是打印时代码浮渣，速度稍慢，但是基本上可以忽略不计，因为只有少数状态需要打印。
注意要gets读入，有空串的情况。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 1000+10;int dp[maxn][maxn];char str[maxn];int n;bool match(char a,char b) {    if( a==‘(‘&&b==‘)‘||a==‘[‘&&b==‘]‘ )        return true;    else        return false;    }void solve() {    for(int i = 0; i < n; i++) {        dp[i+1][i] = 0;        dp[i][i] = 1;    }    for(int i = n-2; i >= 0; i--) {        for(int j = i+1; j < n; j++) {            dp[i][j] = n;            if(match(str[i],str[j]))                dp[i][j] = min(dp[i][j],dp[i+1][j-1]);            for(int k = i; k < j; k++)                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]);        }    }}void print(int i,int j) {    if(i>j) return ;    if(i==j){       if(str[i]==‘(‘||str[i]==‘)‘ )            printf("()");       else        printf("[]");       return;    }    int ans = dp[i][j];    if(match(str[i],str[j]) && ans==dp[i+1][j-1]) {        printf("%c",str[i]);        print(i+1,j-1);        printf("%c",str[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(){//    freopen("in.txt","r",stdin);//    int T;//    scanf("%d",&T);//    getchar();    while(gets(str)) {        n = strlen(str);        solve();        print(0,n-1);        printf("\n");    }    return 0;}

 

POJ 1141 输出正确的括号匹配(最少添加)


联系
我们