1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
typedef long long LL;
#define clr(x) memset((x),0,sizeof(x))
#define inf 0x3f3f3f3f
using namespace std;
char str[1000];
int dp[110][110];
int head[110][110];
bool vis[110];
bool ok(int i,int j)
{
if((str[i]==')'&&str[j]=='(')||(str[i]==']'&&str[j] =='['))
return true;
return false;
}
int dfs(int l,int r)
{
if(r<=l) return dp[l][r] = 0;
if(dp[l][r]!=-1) return dp[l][r];
int ans = 0;
if(ok(r,l))
{
ans = max(ans,dfs(l+1,r-1)+1);
head[l][r] = -1;
}
for(int i =l;i<r;i++)
{
ans = max(ans,dfs(l,i)+dfs(i+1,r));
if(ans == dfs(l,i)+dfs(i+1,r))
{
head[l][r] = i;
}
}
//printf(" %d %d %d %d\n",l,r,head[l][r],ans);
return dp[l][r] = ans;
}
void mark(int l,int r)
{
if(r<=l) return ;
if(head[l][r] ==-1) {
vis[l] = vis[r] = 1;
// printf("%d %d\n",l,r);
mark(l+1,r-1);
return ;
}
int t = head[l][r];
mark(l,t);
mark(t+1,r);
}
int main()
{
scanf("%s",str);
{
memset(dp,-1,sizeof dp);
memset(vis,0,sizeof vis);
memset(head,0,sizeof head);
int len = strlen(str);
int ans = dfs(0,len-1);
mark(0,len-1);
// printf("%d\n",ans);
for(int i =0;i<len;i++)
{
if(vis[i]) putchar(str[i]);
else {
if(str[i]=='('||str[i]==')')
{
printf("()");
}
else{
printf("[]");
}
}
}
putchar('\n');
}
return 0;
}
|