111qqz的小窝

老年咸鱼冲锋!

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.。。。要分这段区间是否中间有划分两种情况。。具体见代码。。。

 

 

说点什么

1 评论 在 "poj 1141 Brackets Sequence (区间dp,括号匹配,记录路径)"

提醒
排序:   最新 | 最旧 | 得票最多

边界情况会有问题
需要在初始化的时候加上
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
dp[i + 1][i] = 0;
}

wpDiscuz