首页 > 代码库 > POJ 1141 Brackets Sequence (区间dp 记录路径)
POJ 1141 Brackets Sequence (区间dp 记录路径)
题目大意:
给出一种不合法的括号序列,要求构造出一种合法的序列,使得填充的括号最少。
思路分析:
如果只要求输出最少的匹配括号的数量,那么就是简单的区间dp
dp[i][j]表示 i - j 之间已经合法了最少添加的括号数。
转移 就是 dp[i] [j] = min (dp[i+1][j]+1 , dp[ i+ 1] [ k -1 ] + dp[k+1] [j] (i k 位置的括号匹配))
其次我们要记录路径,你发现 如果 dp [i] [j] 是由 dp [i+1] [j] 转移过来的。那么第 i 个括号是一个多余存在的。所以首先我们就把这些位置标记。输出的时候不仅输出自己还要输出与之匹配的括号。。。
然后那些是通过后面有括号与之匹配而转移过来的。我们就可以把这两个位置标记。
那么这些位置就可以直接输出自己。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; char str[205]; int dp[105][105]; int pre[105][105]; int mk[105]; void mark(int pos,int n) { if(pos>=n)return; if(pre[pos][n]==-1) { mark(pos+1,n); } else { mk[pos]=1; mk[pre[pos][n]]=1; mark(pos+1,pre[pos][n]-1); mark(pre[pos][n],n); } } int main() { scanf("%s",str+1); int n=strlen(str+1); memset(dp,0,sizeof dp); memset(mk,0,sizeof mk); memset(pre,-1,sizeof pre); for(int i=1; i<=n; i++)dp[i][i]=1; for(int i=n-1; i>=1; i--) { for(int j=i+1; j<=n; j++) { dp[i][j]=dp[i+1][j]+1; pre[i][j]=-1; for(int k=i+1; k<=j; k++) { if(str[i]=='('&&str[k]==')' || str[i]=='['&&str[k]==']') { if(dp[i+1][k-1]+dp[k+1][j]<dp[i][j]) { pre[i][j]=k; dp[i][j]=dp[i+1][k-1]+dp[k+1][j]; } } } } } mark(1,n); for(int i=1; i<=n; i++) if(mk[i]!=1) { if(str[i]=='(' || str[i]==')')printf("()"); else printf("[]"); } else { putchar(str[i]); } puts(""); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。