简单区间DP (有空串... ...)
Time Limit: 4500MS | Memory Limit: Unknown | 64bit IO Format: %lld & %llu |
Description
Let us define a regular brackets sequence in the following way:
- Empty sequence is a regular sequence.
- If S is a regular sequence, then (S) and [S] are both regular sequences.
- 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 a1a2...an is called a subsequence of the string b1b2...bm, if there exist such indices 1 ≤ i1 < i2 < ... < in ≤ m, that aj=bij for all 1 ≤ j ≤ n.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.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
1 ([(]
Sample Output
()[()]
Source
/* *********************************************** Author :CKboss Created Time :2015年02月11日 星期三 16时15分08秒 File Name :ZOJ1463.cpp ************************************************ */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> using namespace std; const int maxn=300; const int INF=0x3f3f3f3f; char str[maxn]; int n; int dp[maxn][maxn]; bool match(int a,int b) { if((str[a]=='('&&str[b]==')')||(str[a]=='['&&str[b]==']')) return true; return false; } void PRINT(int l,int r) { if(l==r) { if(str[l]=='('||str[l]==')') { putchar('('); putchar(')'); } if(str[l]=='['||str[l]==']') { putchar('['); putchar(']'); } return ; } else if(l>r) return ; int pos=-1; int temp=INF; if(match(l,r)) temp=dp[l+1][r-1]; for(int i=l;i+1<=r;i++) if(dp[l][i]+dp[i+1][r]<temp) { pos=i; temp=dp[l][i]+dp[i+1][r]; } if(pos==-1) { putchar(str[l]); PRINT(l+1,r-1); putchar(str[r]); } else { PRINT(l,pos); PRINT(pos+1,r); } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T_T,flag=0; scanf("%d",&T_T); getchar(); while(T_T--) { gets(str); memset(str,0,sizeof(str)); gets(str); n=strlen(str); if(n==0) { if(flag++) putchar(10); putchar(10); continue; } /// DP memset(dp,63,sizeof(dp)); for(int i=0;i<n;i++) dp[i][i]=1; for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i>j) dp[i][j]=0; for(int len=2;len<=n;len++) { for(int i=0;i+len-1<n;i++) { /// i...j int j=i+len-1; if(match(i,j)) dp[i][j]=min(dp[i][j],dp[i+1][j-1]); for(int k=i;k+1<=j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); } } if(flag++) putchar(10); PRINT(0,n-1); putchar(10); } return 0; }