//o(∩_∩)o...哈哈，我回来做题了……
POJ1141是一个经典DP题，是一个“历史遗留”问题了。
一个简单版本
WOJ1077：Dragonflywww
http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1077
题目描述：
给出一个由(、)、[、]组成的字符串，添加最少的括号使得所有的括号匹配，输出最后得到的字符串。
解题思路：
用DP求最少需要括号数：以p从1到n（字符串长度），记录下从i到i+p需要添加的最少括号数f[i][j],同时记录下中间需要添加括号的位置pos[i][j]——为-1表示不需要添加。这种方法我原来就知道，所以过了WOJ1077。
最麻烦的就是添加括号构造字符串了，这里借鉴别人的方法用递归实现，程序里写得很清楚了，要利用pos[i][j]。
1
/** *//*************************************************************************
2
Author: littlekid
3Created Time: 1/9/2008 7:04:26 PM
4Problem Source: POJ1141
5Description:
6
************************************************************************/
7
# include <stdio.h>
8# include <string.h>
9# include <stdlib.h>
10
11# define N 222
12
13const int maxint=0x7FFFFFFF;
14
15int f[ N ][ N ], pos[ N ][ N ];
16char s[ N ];
17int n;
18
19inline int MIN( int a, int b )
20
{
21 return a > b ? b : a;
22}
23
24void init()
25{
26 scanf( "%s", &s );
27}
28
29void output()
30{
31 printf( "%d\n", f[ 1 ][ n ] );
32 for ( int i = 1; i <= n; i ++ )
33
{
34 for ( int j = 1; j <= n; j ++ )
35 {
36 printf( "%c ", f[ i ][ j ] );
37
}
38 printf( "\n" );
39 }
40}
41
42void recur(int beg, int end)
43{
44 if( beg > end ) return ;
45
46 if( beg == end )
47 {
48 if( s[ beg ] == '(' || s[ beg ] == ')' )
49 {
50 printf( "()" );
51 }
52 else printf( "[]" );
53 }
54 else
55 {
56 if( pos[ beg ][ end ] == -1 )
57 {
58 if( s[ beg ] == '(' )
59 {
60 printf( "(" );
61 recur( beg+1, end-1 );
62 printf( ")" );
63 }
64 else
65 {
66 printf( "[" );
67 recur( beg+1, end-1 );
68 printf( "]" );
69 }
70 }
71 else
72 {
73 recur( beg, pos[ beg ][ end ] );
74 recur( pos[ beg ][ end ]+1, end );
75 }
76 }
77}
78
79int DP()
80{
81 n = strlen( s );
82 memset( f, 0, sizeof( f ));
83
84 for ( int i = n; i > 0; i -- )
85 {
86 s[ i ] = s[ i-1 ];
87 f[ i ][ i ] = 1;
88 }
89
90 int tmp;
91 for ( int p = 1; p <= n; p ++ )
92 {
93 for ( int i = 1; i <= n-p; i ++ )
94 {
95 int j = i + p;
96 f[ i ][ j ] = maxint;
97 if ( ( s[ i ] == '(' && s[ j ] == ')' ) || ( s[ i ] == '[' && s[ j ] == ']' ) )
98 {
99 tmp = f[ i+1 ][ j-1 ];
100 if ( tmp < f[ i ][ j ] )
101 {
102 f[ i ][ j ] = tmp;
103 }
104 }
105 pos[ i ][ j ] = -1;
106 for ( int k = i; k < j; k ++ )
107 {
108 tmp = f[ i ][ k ] + f[ k+1 ][ j ];
109 if ( tmp < f[ i ][ j ] )
110 {
111 f[ i ][ j ] = tmp;
112 pos[ i ][ j ] = k;
113 }
114 }
115 }
116 }
117 return f[ 1 ][ n ];
118}
119
120int main()
121{
122 //while ( scanf( "%s", &s) != EOF ){
123 init();
124 DP();
125 //output();
126 recur( 1, n );
127 printf( "\n" );
128 //}
129 return 0;
130}
131
132