Poj 1141 Brackets Sequence

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

()[()]

题意

题目描述： 定义合法的括号序列如下： 1 空序列是一个合法的序列 2 如果S是合法的序列，则(S)和[S]也是合法的序列 3 如果A和B是合法的序列，则AB也是合法的序列 例如：下面的都是合法的括号序列 (), [], (()), ([]), ()[], ()[()] 下面的都是非法的括号序列 (, [, ), )(, ([)], ([(] 给定一个由’(‘, ‘)’, ‘[‘, 和 ‘]’ 组成的序列，找出以该序列为子序列的最短合法序列。

思路

区间DP,分两种情况处理, d[i][j]代表从i到j最少需要加的括号数,s[]代表括号序列 第一种情况:如果s[i]==s[j] ,就是s[i]和s[j]已经匹配好了,那么d[i][j]=d[i+1][j-1] 第二种情况:如果s[i]和s[j]不匹配,将i->j分成两部分d[i][k]+d[k+1][j] d[i][j]=min(d[i][k]+d[k+1][j],d[i][j]); 打印时也是这样分开考虑

代码

#include<cstdio> #include<cstring> #include<algorithm> #define inf 1e9 using namespace std; int d[101][101]; char s[101]; int len; bool match(char a,char b) { if((a=='('&&b==')')||(a=='['&&b==']')) return true; return false; } void print(int i,int j) { if(i>j) return; if(i==j) { if(s[i]=='('||s[i]==')') printf("()"); if(s[i]=='['||s[i]==']') printf("[]"); return; } int ans=d[i][j]; if(ans==d[i+1][j-1]&&match(s[i],s[j])) { printf("%c",s[i]); print(i+1,j-1); printf("%c",s[j]); return; } for(int k=i;k<j;k++) if(ans==d[i][k]+d[k+1][j]) { print(i,k); print(k+1,j); return; } } int main() { scanf("%s",s); len=strlen(s); for(int i=0;i<len;i++) d[i][i]=1; for(int l=1;l<len;l++) for(int i=0;i<len-l;i++) { int j=i+l; d[i][j]=inf; if(match(s[i],s[j])) d[i][j]=d[i+1][j-1]; for(int k=i;k<j;k++) d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]); } print(0,len-1); printf("\n"); return 0; }