Brackets Sequence
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 19636 | Accepted: 5437 | 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.
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
//终于找到黑书上的第一个动规了
//本来1Y的、郁闷的是我乐极生悲了，在空串的时候我不输空我居然输了个0出来、、、
//昨晚找到的这题，升级版吧、黑书上只是求出最少需要添加几个，而这里需要打印出来
//我利用st数组记录状态的转移，写的有点复杂、哈哈，明天就回家
//今天的打算就是把这题A掉、呵呵、回家休养生息几天、
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #include <cmath> #include <vector> using namespace std; struct node { bool flag; int i1,j1,i2,j2; }; node st[102][102]; int dp[122][122]; bool b[122]; char s[122]; int l; void dfs (node p) { if(p.flag==0) { if(p.i1==p.j1) { b[p.i1]=1; return; } else { if(p.i1>p.j1) return; } dfs(st[p.i1][p.j1]); } else { dfs(st[p.i1][p.j1]); dfs(st[p.i2][p.j2]); } } void del() { int i,k,j,t; i=0; dp[0][0]=1; st[i][i].flag=0; st[i][i].i1=st[i][i].j1=i; for(i=1;i<l;i++) { dp[i][i]=1,dp[i][i-1]=0; st[i][i].flag=0; st[i][i].i1=st[i][i].j1=i; st[i][i-1].flag=0; st[i][i-1].i1=i; st[i][i-1].j1=i-1; } for(k=2;k<=l;k++) { for(i=0;i+k<=l;i++) { j=i+k-1; dp[i][j]=1000; if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')) { dp[i][j]=dp[i+1][j-1]; st[i][j].flag=0; st[i][j].i1=i+1; st[i][j].j1=j-1; } for(t=i;t<j;t++) { if(dp[i][j]>dp[i][t]+dp[t+1][j]) { dp[i][j]=dp[i][t]+dp[t+1][j]; st[i][j].flag=1; st[i][j].i1=i; st[i][j].j1=t; st[i][j].i2=t+1; st[i][j].j2=j; } } } } memset(b,0,sizeof(b)); dfs(st[0][l-1]); for(i=0;i<l;i++) if(b[i]) { if(s[i]=='('||s[i]==')') printf("%c%c",'(',')'); else printf("%c%c",'[',']'); } else printf("%c",s[i]); printf("\n"); } int main() { while(gets(s)!=NULL) { if(l=strlen(s)) del(); else printf("\n"); } return 0; }