[poj P1141] Brackets Sequence
Time Limit: 1000MS Memory Limit: 65536K 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
括号匹配的变形题。
这题的范围,非常的适合区间dp。
那么我们来设计一个dp。设f[i][j]为将原串中i~j全部匹配好需要增加的字符数量。
则:
先赋值正无穷。
对于j-i+1==1 ---> f[i][j]=1
对于j-i+1==2 ---> f[i][j]=cmp(a[i],a[j])?0:2
对于j-i+1>=3 ---> f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]),if (cmp(a[i],a[j])) f[i][j]=min(f[i][j],f[i+1][j-1])
其中cmp代表两个字符是否匹配。
那么这样,就轻松计算出了f[1][n]。
这一题要让我们输出方案。
一般dp的题都可以用dfs递归输出方案。
具体实现应该很好想吧!但是有些细节和顺序容易搞错。
下面先给出几组数据(不一定完全相同,有spj没关系):
in1:
[]]]]
out1:
[][][][]
in2:
)))(((
out2:
()()()()()()
in3:
“空串”
out3:
“空串”
in4:
([][]([]()))[()]([])
out4:
([][]([]()))[()]([])
code:
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; ; int n,f[N][N]; char a[N]; bool vis[N]; int cmp(int x,int y) { ; ; ; } void dfs(int l,int r) { if (l>r) return; if (l==r) { if (vis[l]||vis[r]) return; if (a[l]=='(') printf("()"); else if (a[l]==')') printf("()"); else if (a[l]=='[') printf("[]"); else if (a[l]==']') printf("[]"); vis[l]=vis[r]=; return; } for (int i=l; i<r; i++) ][r]==f[l][r]) {dfs(l,i),dfs(i+,r); return;} if (cmp(l,r)) { vis[l]=vis[r]=; printf("%c",a[l]); dfs(l+,r-); printf("%c",a[r]); return; } } int main() { scanf(),n=strlen(a+); ) ; memset(f,,sizeof f); ; i<=n; i++) f[i][i]=; ; i<n; i++) )) f[i][i+]=; ]=; ; l<=n; l++) { ; i<=n-l+; i++) { ; ][j-]; ][j]); } } dfs(,n); cout<<endl; ; }