Brackets Sequence

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 23638		Accepted: 6665		Special Judge

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.

The input file contains at most 100 brackets (characters ‘(‘, ‘)‘, ‘[‘ and ‘]‘) that are situated on a single line without any other characters among them.

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.

([(]

()[()]

题目分析：
　　显然题目是要求我们为一个输入序列添加最少的“[”或者“(”等符号来使之可以配对。要配对的办法肯定有很多种，我们检测到每一个括号都给他配对，那么最终多出了一倍的符号，这样肯定是配对的但是不符合最少的。因此我们采用一个区间DP的方法。pos[i][j]表示第i个和第j个字符之间的需要隔开的位置，若是匹配的则为-1，dp[i][j]表示第i个和第j个字符之间需要添加的字符数。具体见如下Java代码注释。

 1 import java.util.*;
 2 public class BracketsSequence1141 {
 3     private static char s[]=new char[105];//接受控制台的输入。
 4     private int len;//输入字符串的长度
 5     private int dp[][]=new int[105][105];//dp[i][j]，从i到j需要插入的最小字符数
 6     private int pos[][]=new int[105][105];//pos[i][j],字符i与j是否匹配，若是则为-1，若不是则记录隔开的位置
 7     private void print(int i,int j){
 8         //输出结果
 9         if(i>j)
10             return;
11         if(i==j){
12             if(s[i]==‘(‘||s[i]==‘)‘)
13                 System.out.print("()");
14             else
15                 System.out.print("[]");
16         }
17         else{
18             if(pos[i][j]==-1){//如果字符是匹配的
19                 System.out.print(s[i]);
20                 print(i+1,j-1);
21                 System.out.print(s[j]);
22             }
23             else{//字符不匹配
24                 print(i,pos[i][j]);
25                 print(pos[i][j]+1,j);
26             }
27         }
28     };
29     private void getDP(){
30         int inf=0x7fffffff;
31         int i,j,k,mid;
32         int len=s.length;
33         for(i=0;i<len;i++){
34             for(j=0;j<len;j++){
35                 dp[i][j]=0;
36             }
37             dp[i][i]=1;
38         }
39         for(k=1;k<len;k++){
40             for(i=0;i+k<len;i++){
41                 j=i+k;//表示不断地分隔，比较不同字符之间是否匹配
42                 dp[i][j]=inf;//表示目前不可匹配
43                 if((s[i]==‘(‘&&s[j]==‘)‘)||(s[i]==‘[‘&&s[j]==‘]‘)){
44                     //表示字符配对
45                     dp[i][j]=dp[i+1][j-1];
46                     pos[i][j]=-1;
47                 }
48                 //若字符不配对或者其他，表示寻找更少的配对数
49                 for(mid=i;mid<j;mid++){
50                     if(dp[i][j]>dp[i][mid]+dp[mid+1][j]){
51                         dp[i][j]=dp[i][mid]+dp[mid+1][j];
52                         pos[i][j]=mid;
53                     }
54                 }
55             }
56         }
57     }
58     public static void main(String[] args){
59         Scanner sc = new Scanner(System.in);
60         //String temp=null;
61         BracketsSequence1141 A=new BracketsSequence1141();
62         s=sc.nextLine().toCharArray();
63         if(s.length==0){
64             System.out.println();
65         }
66         else{
67             A.getDP();
68             A.print(0,s.length-1);
69         }    
70     }    
71 }