简单区间DP (有空串… …)
Brackets sequence
Time Limit:4500MSMemory Limit:Unknown64bit IO Format:%lld & %llu
Submit
Description
Let us define a regular brackets sequence in the following way:
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…anis called a subsequence of the string b1b2…bm, if there exist such indices 1 ≤ i1< i2< … < in≤ m, that aj=bijfor all 1 ≤ j ≤ n.
InputThe 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.
OutputFor 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 Input1([(]Sample Output()[()]
Source
Root :: AOAPC II: Beginning Algorithm Contests (Second Edition) (Rujia Liu) :: Chapter 9. Dynamic Programming ::Examples
Submit
/* ***********************************************Author:CKbossCreated 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; }/// DPmemset(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…jint 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;}
，快乐要有悲伤作陪，雨过应该就有天晴。
