//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
3 Created Time: 1/9/2008 7:04:26 PM
4 Problem Source: POJ1141
5 Description:
6 ************************************************************************/
7 # include <stdio.h>
8 # include <string.h>
9 # include <stdlib.h>
10
11 # define N 222
12
13 const int maxint=0x7FFFFFFF;
14 typedef long long int64;
15 const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
16
17 int f[ N ][ N ], pos[ N ][ N ];
18 char s[ N ];
19 int n;
20
21 inline int MIN( int a, int b )
22 {
23 return a > b ? b : a;
24 }
25
26 void init()
27 {
28 scanf( "%s", &s );
29 }
30
31 void output()
32 {
33 printf( "%d\n", f[ 1 ][ n ] );
34 for ( int i = 1; i <= n; i ++ )
35 {
36 for ( int j = 1; j <= n; j ++ )
37 {
38 printf( "%c ", f[ i ][ j ] );
39 }
40 printf( "\n" );
41 }
42 }
43
44 void recur(int beg, int end)
45 {
46 if( beg > end ) return ;
47
48 if( beg == end )
49 {
50 if( s[ beg ] == '(' || s[ beg ] == ')' )
51 {
52 printf( "()" );
53 }
54 else printf( "[]" );
55 }
56 else
57 {
58 if( pos[ beg ][ end ] == -1 )
59 {
60 if( s[ beg ] == '(' )
61 {
62 printf( "(" );
63 recur( beg+1, end-1 );
64 printf( ")" );
65 }
66 else
67 {
68 printf( "[" );
69 recur( beg+1, end-1 );
70 printf( "]" );
71 }
72 }
73 else
74 {
75 recur( beg, pos[ beg ][ end ] );
76 recur( pos[ beg ][ end ]+1, end );
77 }
78 }
79 }
80
81 int DP()
82 {
83 n = strlen( s );
84 memset( f, 0, sizeof( f ));
85
86 for ( int i = n; i > 0; i -- )
87 {
88 s[ i ] = s[ i-1 ];
89 f[ i ][ i ] = 1;
90 }
91
92 int tmp;
93 for ( int p = 1; p <= n; p ++ )
94 {
95 for ( int i = 1; i <= n-p; i ++ )
96 {
97 int j = i + p;
98 f[ i ][ j ] = maxint;
99 if ( ( s[ i ] == '(' && s[ j ] == ')' ) || ( s[ i ] == '[' && s[ j ] == ']' ) )
100 {
101 tmp = f[ i+1 ][ j-1 ];
102 if ( tmp < f[ i ][ j ] )
103 {
104 f[ i ][ j ] = tmp;
105 }
106 }
107 pos[ i ][ j ] = -1;
108 for ( int k = i; k < j; k ++ )
109 {
110 tmp = f[ i ][ k ] + f[ k+1 ][ j ];
111 if ( tmp < f[ i ][ j ] )
112 {
113 f[ i ][ j ] = tmp;
114 pos[ i ][ j ] = k;
115 }
116 }
117 }
118 }
119 return f[ 1 ][ n ];
120 }
121
122 int main()
123 {
124 //while ( scanf("%s", &s ) != EOF ){
125 init();
126 DP();
127 //output();
128 recur( 1, n );
129 printf( "\n" );
130 //}
131 return 0;
132 }
133
134
posted on 2008-01-09 21:40
R2 閱讀(1315)
評論(0) 編輯 收藏 引用 所屬分類:
Problem Solving