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题目链接：Brackets Sequence
一个输入问题Debug 1个多小时 hehe~~~
题意： 求串x，要求x里的左右括号是平衡匹配的,并且给出的串是x的子串 输出最短的x Special Judge 分析： 区间DP记录路径 dp[i][j]表示将区间[i,j]的串能变成的最短的串的长度 显然这 分析：里以子串求目标串只能 添加字符 所有状态转移： 1.dp[i][j] = dp[i+1][j]+2 2.在区间[i+1,j]找到一个 k 满足match(s[i],s[k]) dp[i][j] = dp[i+1][k-1]+dp[k+1][j]+2
要注意的是，输入会有空行。。。特判下。。。。
#define mem(a,x) memset(a,x,sizeof(a)) #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; /* 题意： 求串x，要求x里的左右括号是平衡匹配的,并且给出的串是x的子串 输出最短的x Special Judge 分析： 区间DP记录路径 dp[i][j]表示将区间[i,j]的串能变成的最短的串的长度 显然这里以子串求目标串只能 添加字符 所有状态转移： 1.dp[i][j] = dp[i+1][j]+2 2.在区间[i+1,j]找到一个 k 满足match(s[i],s[k]) dp[i][j] = dp[i+1][k-1]+dp[k+1][j]+2 */ const int N = 111; int dp[N][N]; struct Node { string s; }p[N][N]; char s[N]; string getmatch(char c) { if (c == '('||c == ')') return "()"; if (c == '['||c == ']') return "[]"; } string getright(char c) { if (c == '(') return ")"; if (c == '[') return "]"; } string getleft(char c) { if (c == ')') return "("; if (c == ']') return "["; } bool match(char a,char b) { return (a=='('&&b==')')||(a == '['&&b == ']'); } int DP(int i,int j) { if (i > j) { p[i][j].s.clear(); return 0; } if (~dp[i][j]) return dp[i][j]; if (i == j) { p[i][j].s = getmatch(s[i]); return dp[i][j] = 2; } string path ; dp[i][j] = DP(i+1,j)+2; if (s[i] == '('||s[i] == '[') path = s[i] + p[i+1][j].s + getright(s[i]); else path = getleft(s[i]) + s[i] + p[i+1][j].s; for (int k = i+1;k <=j;++k) { if (match(s[i],s[k])) { if (DP(i+1,k-1)+DP(k+1,j)+2<dp[i][j]) { dp[i][j] = DP(i+1,k-1)+DP(k+1,j)+2; path = s[i] + p[i+1][k-1].s + s[k] + p[k+1][j].s; } } } p[i][j].s = path; return dp[i][j]; } int main() { while (gets(s)) { if (strlen(s) == 0) { puts(""); continue; } mem(dp,-1);int n = strlen(s)-1; DP(0,n); // cout<<DP(0,n)<<endl; cout<<p[0][n].s<<endl; } return 0; } /* ([)[)[))(] */