UVA1626 / ZOJ1463 Brackets sequence 区间DP - c++编程基础

TOP

UVA1626 / ZOJ1463 Brackets sequence 区间DP

2015-07-20 17:18:00 来源: 作者: 【大中小】浏览:4次

Tags：UVA1626 ZOJ1463 Brackets sequence 区间

简单区间DP (有空串... ...)

Brackets sequence

Time Limit: 4500MS

Memory Limit: Unknown

64bit IO Format: %lld & %llu

Submit Status

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 a₁a₂...a_n is called a subsequence of the string b₁b₂...b_m, if there exist such indices 1 ≤ i₁ < i₂ < ... < i_n ≤ m, that a_j=b_{i_j} 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

Root :: AOAPC II: Beginning Algorithm Contests (Second Edition) (Rujia Liu) :: Chapter 9. Dynamic Programming :: Examples

Submit Status

/* ***********************************************
Author        :CKboss
Created Time  :2015年02月11日 星期三 16时15分08秒
File Name     :ZOJ1463.cpp
************************************************ */

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             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]
             
              j) dp[i][j]=0; for(int len=2;len<=n;len++) { for(int i=0;i+len-1


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Search Insert Position	下一篇：leetcode_56_Merge Intervals

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: