Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给出一个括号序列，要求添加最少的括号，使得这个序列变成合法的括号匹配，输出最后的序列。
思路：区间dp。。。有了那么一点思路。。。我们可以用dp[i][j]表示区间[i,j]的序列最少需要添加几个符号使得匹配。。转移的话。。。和之前差不多。。dp[i][j] = dp[i+1][j-1] (s[i]与s[j])匹配。。。不匹配的话也是找中间某个点。。。初始化的话。。要变成最大值。。。比较没思路的是输出括号序列这部分。。。
参考了这篇题解：参考题解
记录路径的思路是。。。记录转移的点。。。
cut[i][j]表示的是区间[i,j]的最优值是由点cut[i][j]这里划分得到的。。。
cut[i][j]为-1表示区间[i,j]的最优值不是从中间分成两部分得到。。。
打印路径的时候。。。如果[i,j]的长度小于等于0.。直接return.
如果长度为1.。。直接输出。。。
如果长度大于1.。。。要分这段区间是否中间有划分两种情况。。具体见代码。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月25日 星期一 15时55分47秒
4File Name :code/poj/1141.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33char s[105];
34int dp[105][105]; //dp[i][j]表示区间[i,j]最少需要添加多少字符达到匹配。
35int cut[105][105] ; //记录一段区间是在哪里断开最优，是为了记录路径，打印括号
36bool check(char a,char b)
37{
38 if (a=='['&&b==']') return true;
39 if (a=='('&&b==')') return true;
40 return false;
41}
42
43void print(int i ,int j)
44{
45 if (i>j) return ;
46 if (i==j)
47 {
48 if (s[i]=='('||s[i]==')') printf("()");
49 if (s[i]=='['||s[i]==']') printf("[]");
50 return ;
51 }
52 if (cut[i][j]==-1)
53 {
54 printf("%c",s[i]);
55 print(i+1,j-1);
56 printf("%c",s[j]);
57 }
58 else
59 {
60 print(i,cut[i][j]);
61 print(cut[i][j]+1,j);
62 }
63}
64int main()
65{
66 #ifndef ONLINE_JUDGE
67 freopen("code/in.txt","r",stdin);
68 #endif
69
70 scanf("%s",s);
71
72 int len = strlen(s);
73 ms(dp,0x3f);
74 ms(cut,-1);
75 for ( int i = 0 ; i <=len ; i++) dp[i][i] = 1;
76
77 for ( int l = 1 ; l < len ; l++)
78 {
79 for ( int i = 0 , j = l ; j < len ; i++,j++)
80 {
81 dp[i][j] = inf;
82 if (check(s[i],s[j]))
83 {
84 dp[i][j] = dp[i+1][j-1]; //当前匹配的话，就不需要增加字符
85 cut[i][j] = -1;
86 }
87
88 for ( int k = i ; k < j ; k++)
89 if (dp[i][j]>dp[i][k]+dp[k+1][j])
90 {
91 dp[i][j] = dp[i][k] + dp[k+1][j];
92 cut[i][j] = k;
93 }
94 }
95 }
96
97 print(0,len-1);
98 printf("\n");
99
100
101 #ifndef ONLINE_JUDGE
102 fclose(stdin);
103 #endif
104 return 0;
105}