POJ 1141 – Brackets Sequence

题目链接:POJ – 1141

区间DP。$f(l,r)$表示区间$[l, r]$最少要加几个括号才能匹配,显然边界条件为$f(i,i)= 1$。考虑将这个区间分成$[l,k]$和$[k + 1, r]$两段,$l \leq k < r$,则$f(l,r) = \min \{ f(l, k), f(k + 1, r) \}$。

当$l$和$r$可以匹配的时候,考虑转移到$f(l + 1, r – 1)$的情况。

对于方案输出,使用辅助数组记录最优的分割位置,递归打印$[l,r]$区间匹配后的结果——首先,区间长度为1的时候直接打印一对括号(如果区间内是小括号则打印小括号,是中括号则打印中括号);当区间长度不为一的时候,根据辅助数组记录的信息,如果有最优分割位置$k$,则先递归打印$[l,k]$,再打印$[k + 1, r]$,如果没有,则将当前位打印,再递归打印$[l+1, r -1]$,然后加上当前位的匹配括号。

 

说点什么

avatar
50
  Subscribe  
提醒