poj 1141 Brackets Sequence (区间dp,括号匹配,记录路径)

poj 1141题目链接

 

题意:给出一个括号序列,要求添加最少的括号,使得这个序列变成合法的括号匹配,输出最后的序列。

思路:区间dp。。。有了那么一点思路。。。我们可以用dp[i][j]表示区间[i,j]的序列最少需要添加几个符号使得匹配。。转移的话。。。和之前差不多。。dp[i][j] = dp[i+1][j-1] (s[i]与s[j])匹配。。。不匹配的话也是找中间某个点。。。初始化的话。。要变成最大值。。。比较没思路的是输出括号序列这部分。。。

参考了这篇题解:参考题解

记录路径的思路是。。。记录转移的点。。。

cut[i][j]表示的是区间[i,j]的最优值是由点cut[i][j]这里划分得到的。。。

cut[i][j]为-1表示区间[i,j]的最优值不是从中间分成两部分得到。。。

打印路径的时候。。。如果[i,j]的长度小于等于0.。直接return.

如果长度为1.。。直接输出。。。

如果长度大于1.。。。要分这段区间是否中间有划分两种情况。。具体见代码。。。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz