poj 1141 Brackets Sequence（区间DP）

题目:

转载：

定义合法的括号序列如下：

1 空序列是一个合法的序列

2 如果S是合法的序列，则(S)和[S]也是合法的序列

3 如果A和B是合法的序列，则AB也是合法的序列

例如：下面的都是合法的括号序列

(),  [],  (()),  ([]),  ()[],

 ()[()]

下面的都是非法的括号序列

(,  [,  ),  )(,  ([)],

 ([(] 

给定一个由‘(‘,  ‘)‘,  ‘[‘, 和 ‘]‘

组成的序列，找出以该序列为子序列的最短合法序列。

d[i][j]为输入序列从下标i到下标j最少需要加多少括号才能成为合法序列。0<=i<=j<len

(len为输入序列的长度)。

c[i][j]为输入序列从下标i到下标j的断开位置，如果没有断开则为-1。

当i==j时，d[i][j]为1

当s[i]==‘(‘ && s[j]==‘)‘ 或者 s[i]==‘[‘ &&

s[j]==‘]‘时，d[i][j]=d[i+1][j-1]

否则d[i][j]=min{d[i][k]+d[k+1][j]} i<=k<j ，

 c[i][j]记录断开的位置k

采用递推方式计算d[i][j]

输出结果时采用递归方式输出print(0, len-1)

输出函数定义为print(int i, int j)，表示输出从下标i到下标j的合法序列

当i>j时，直接返回，不需要输出

当i==j时，d[i][j]为1，至少要加一个括号，如果s[i]为‘(‘ 或者‘)‘，输出"()"，否则输出"[]"

当i>j时，如果c[i][j]>=0，说明从i到j断开了，则递归调用print(i,

c[i][j]);和print(c[i][j]+1, j);

如果c[i][j]<0，说明没有断开，如果s[i]==‘(‘ 则输出‘(‘、 print(i+1, j-1);

和")"  否则输出"[" print(i+1, j-1);和"]"

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

100

<code>#include &lt;cstdio&gt;</code>

<code>#include &lt;cstring&gt;</code>

<code>using</code>

<code>namespace</code> <code>std;</code>

<code>int</code> <code>dp[107][107];</code>

<code>int</code> <code>c[107][107];</code>

<code>char</code> <code>ch[107];</code>

<code>int</code> <code>len ;</code>

<code>void</code>

<code>mydp()</code>

<code>{</code>

<code>    </code><code>memset(dp,0,</code><code>sizeof</code><code>(dp));</code>

<code>    </code><code>memset(c,0,</code><code>sizeof</code><code>(c));</code>

<code>    </code><code>int</code>

<code>i,j,k,l;</code>

<code>    </code><code>for</code><code>(i = 0; i &lt; len; i++) dp[i][i] = 1;</code>

<code>min;</code>

<code>    </code><code>for</code><code>(l = 1; l &lt; len; l++)</code>

<code>        </code><code>for</code><code>(i = 0; i+l &lt; len; i++)</code>

<code>            </code><code>{</code>

<code>                </code><code>j = i+l;</code>

<code>                </code><code>min=dp[i][i] + dp[i+1][j];</code>

<code>                </code><code>c[i][j] = i;</code>

<code>                </code><code>for</code><code>(k = i+1; k &lt; j; k++)</code>

<code>                </code><code>{</code>

<code>                    </code><code>if</code><code>(dp[i][k]+dp[k+1][j] &lt; min)</code>

<code>                    </code><code>{</code>

<code>                        </code><code>min = dp[i][k] + dp[k+1][j];</code>

<code>                        </code><code>c[i][j] = k;</code>

<code>                    </code><code>}</code>

<code>                </code><code>}</code>

<code>                </code><code>dp[i][j] = min;</code>

<code>                </code><code>if</code><code>( (ch[i] ==</code><code>‘(‘</code>

<code>&amp;&amp; ch[j] ==</code><code>‘)‘</code><code>) || (ch[i] ==</code><code>‘[‘</code>

<code>&amp;&amp; ch[j] ==</code><code>‘]‘</code><code>) )</code>

<code>                    </code><code>if</code><code>(dp[i+1][j-1] &lt; min){</code>

<code>                        </code><code>dp[i][j] = dp[i+1][j-1];</code>

<code>                        </code><code>c[i][j] = -1;</code>

<code>            </code><code>}</code>

<code>}</code>

<code>print(</code><code>int</code>

<code>i,</code><code>int</code>

<code>j)</code>

<code>    </code><code>if</code><code>(i &gt; j)</code><code>return</code><code>;</code>

<code>    </code><code>if</code><code>(i == j)</code>

<code>    </code><code>{</code>

<code>       </code><code>if</code><code>(ch[i]==</code><code>‘(‘</code>

<code>|| ch[i] ==</code><code>‘)‘</code><code>) printf(</code><code>"()"</code><code>);</code>

<code>       </code><code>else</code>

<code>printf(</code><code>"[]"</code><code>);</code>

<code>    </code><code>}</code>

<code>    </code><code>else</code>

<code>        </code><code>if</code><code>(c[i][j] &gt;= 0)</code>

<code>        </code><code>{</code>

<code>            </code><code>print(i,c[i][j]);</code>

<code>            </code><code>print(c[i][j]+1,j);</code>

<code>        </code><code>}</code>

<code>        </code><code>else</code>

<code>            </code><code>if</code><code>(ch[i] ==</code><code>‘(‘</code><code>)</code>

<code>              </code><code>{</code>

<code>                  </code><code>printf(</code><code>"("</code><code>);</code>

<code>                  </code><code>print(i+1,j-1);</code>

<code>                  </code><code>printf(</code><code>")"</code><code>);</code>

<code>              </code><code>}</code>

<code>            </code><code>else</code>

<code>                </code><code>printf(</code><code>"["</code><code>);</code>

<code>                </code><code>print(i+1,j-1);</code>

<code>                </code><code>printf(</code><code>"]"</code><code>);</code>

<code>printdp()</code>

<code>    </code><code>for</code><code>(</code><code>int</code>

<code>i = 0; i &lt; len; i++)</code>

<code>        </code><code>{</code><code>for</code><code>(</code><code>int</code>

<code>j = 0; j &lt; len; j++)</code>

<code>        </code><code>printf(</code><code>"%d "</code><code>,dp[i][j]);</code>

<code>        </code><code>printf(</code><code>"\n"</code><code>);}</code>

<code>         </code><code>printf(</code><code>"\n"</code><code>);</code>

<code>         </code><code>for</code><code>(</code><code>int</code>

<code>        </code><code>printf(</code><code>"%d "</code><code>,c[i][j]);</code>

<code>int</code>

<code>main()</code>

<code>        </code><code>scanf(</code><code>"%s"</code><code>,ch);</code>

<code>        </code><code>len = strlen(ch);</code>

<code>        </code><code>mydp();</code>

<code>      </code><code>//  printdp();</code>

<code>        </code><code>print(0,len-1);</code>

<code>        </code><code>printf(</code><code>"\n"</code><code>);</code>

<code>    </code><code>return</code>

<code>0;</code>