几乎和Folding是一样的题目，区别是这更简单一点。LRJ黑书里拿做动态规划例题的第一道。
1
#include <cstdio>
2#include <string>
3
4#define min(x,y) ( x < y ? x : y )
5
6int T, m[101][101], L, ch[101][101];
7char str[101];
8
9void dp ();
10int get ( int, int );
11void init ();
12void print ( int, int );
13
14int main ()
15
{
16
//freopen ( "bracket.in", "r", stdin );
17 scanf ( "%d", &T );
18 gets ( str );
19 int i;
20 for ( i = 0; i < T; i ++ )
21
{
22 if ( i )
23 printf ( "\n" );
24 init ();
25 dp ();
26 //printf ( "%d\n", ch[0][L - 1] );
27 print ( 0, L - 1 );
28 printf ( "\n" );
29 //pt ();
30
}
31 return 0;
32
}
33
34void init ()
35{
36 gets ( str );
37 gets ( str );
38 L = strlen ( str );
39 memset ( m, 0, sizeof ( m ) );
40 memset ( ch, 0xff, sizeof ( ch ) );
41}
42
43void dp ()
44{
45 int i, j, p, k, t;
46 for ( i = 0; i < L; i ++ )
47 m[i][i] = 1;
48 for ( p = 1; p <= L; p ++ )
49 {
50 for ( i = 0; i + p < L; i ++ )
51 {
52 int ans = 101;
53 j = i + p;
54 if ( str[i] == '(' && str[j] == ')' || str[i] == '[' && str[j] == ']' )
55 {
56 t = m[i + 1][j - 1];
57 if ( ans > t )
58 ch[i][j] = -2, ans = t;
59 }
60 if ( str[i] == '(' || str[i] == '[' )
61 {
62 t = m[i + 1][j] + 1;
63 if ( ans > t )
64 ch[i][j] = i, ans = t;
65 }
66 if ( str[j] == ')' || str[j] == ']' )
67 {
68 t = m[i][j - 1] + 1;
69 if ( ans > t )
70 ch[i][j] = j, ans = t;
71 }
72 for ( k = i; k < j; k ++ )
73 {
74 t = m[i][k] + m[k + 1][j];
75 if ( ans > t )
76 ch[i][j] = k, ans = t;
77 }
78 m[i][j] = ans;
79 }
80 }
81}
82
83void print ( int i, int j )
84{
85 if ( i > j )
86 return;
87 if ( i == j )
88 {
89 if ( str[i] == '(' || str[i] == ')' )
90 printf ( "()" );
91 else
92 printf ( "[]" );
93 return;
94 }
95 else if ( ch[i][j] == -2 )
96 {
97 printf ( "%c", str[i] );
98 print ( i + 1, j - 1 );
99 printf ( "%c", str[j] );
100 }
101 else if ( ch[i][j] == j )
102 {
103 print ( i, j - 1 );
104 print ( j, j );
105 }
106 else
107 {
108 print ( i, ch[i][j] );
109 print ( ch[i][j] + 1, j );
110 }
111}
112
113