题解：UVA1626 括号序列 Brackets sequence
这是一道区间 $\texttt{dp}$ 的典型题目。
设 $dp_{i,j}$ 表示串中第 $i$ 个到第 $j$ 个括号串最少需要括号才能完全匹配的个数。有两个显然的结论：一是 $dp_{i,i} = 1$，因为一个括号无法匹配，要且仅需要一个括号即能完全匹配；二是合并的时候是从小区间往大区间合并，因为只有计算完小区间的答案才能更新大区间。
对于一个 $i$ 至 $j$ 的区间（$i < j$），可以由在此区间内的任意两个小区间合并得到答案，也就是 $dp_{i,j} = \min (dp_{i,j},dp_{i,k} + dp_{k + 1,j}),i \le k < j$。当然，当 $i$ 与 $j$ 本身匹配时，需要先取个最值 $dp_{i,j} = \min (dp_{i,j},dp_{i + 1,j - 1})$。
题目还需要输出方案，也就是要通过递归由答案倒退过程。f(i,j) 表示要还原的括号的范围。显然 $i = j$ 的时候直接匹配括号的另一半；当 $i$ 与 $j$ 匹配时，直接可以输出这两个括号，问题也就缩小为求 f(i + 1,j - 1)；如果不匹配，就模拟区间 $\texttt{dp}$ 的过程，找到一个符合条件的 $k$,然后分别求解 f(i,k) 与 f(k + 1,j) 就行了。
对于数组初始化的方式，分为三种情况，列举如下：
- $i = j$，就是 $dp_{i,j} = 1$。
- $i > j$，显然此时不成串，为防止干扰，将其设置为 $0$。
- $i < j$，因为区间 $\texttt{dp}$ 要取最小值，所以全部设置为 $\infty$。
最后提醒一下各位对于题目多组数据的一个小提醒：不要忘记初始化！不要忘记组间的空格！不要在最后一组数据这多输出一个空格！可能输入有空串！
完整代码如下：
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
88
89
90
91
92
93
94
95
96
97
98
99
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,INF,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 105;
const int MOD = 1e9 + 7;
inline int read ();
string str;
int n,t,dp[MAX][MAX];
void print (int x,int y);
int main ()
{
t = read ();
while (t--)
{
init (dp);
getline (cin,str);
getline (cin,str);
int n = str.size ();
if (!n)
{
puts ("");
if (t) puts ("");
continue;
}
for (int i = 0;i < n;++i)
{
for (int j = 0;j < n;++j)
{
if (i == j) dp[i][j] = 1;
else if (i > j) dp[i][j] = 0;
else dp[i][j] = INF;
}
}
for (int j = 0;j < n;++j)
{
for (int i = j - 1;i >= 0;--i)
{
if (str[i] == '(' && str[j] == ')' || str[i] == '[' && str[j] == ']') dp[i][j] = min (dp[i][j],dp[i + 1][j - 1]);
for (int k = i;k < j;++k)
dp[i][j] = min (dp[i][k] + dp[k + 1][j],dp[i][j]);
}
}
print (0,n - 1);
puts ("");
if (t) puts ("");
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
void print (int x,int y)
{
if (x > y) return ;
if (x == y)
{
if (str[x] == '(' || str[x] == ')') printf ("()");
else printf ("[]");
return ;
}
if (((str[x] == '(' && str[y] == ')') || (str[x] == '[' && str[y] == ']')) && dp[x][y] == dp[x + 1][y - 1])
{
printf ("%c",str[x]);
print (x + 1,y - 1);
printf ("%c",str[y]);
return ;
}
for (int k = x;k < y;++k)
{
if (dp[x][y] == dp[x][k] + dp[k + 1][y])
{
print (x,k);print (k + 1,y);
return ;
}
}
}
|
