poj 1141 Brackets Sequence 括号匹配

本文主要是介绍poj 1141 Brackets Sequence 括号匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给出一个由'(' , ')' ,'[' , ']' 组成的字符串，通过增加最少括号使其匹配。

解法：区间dp，记录下划分位置。PS：用while（scanf！＝ＥＯＦ）会ＷＡ

 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=105;
char str[maxn];
int dp[maxn][maxn], len, flag[maxn][maxn];
bool match(int x, int y){return (str[x]=='('&&str[y]==')')||(str[x]=='['&&str[y]==']');
}
void getmatch(int x){if(str[x]=='('||str[x]==')')printf("()");else printf("[]");
}
int solve(int x, int y){if(x>y)return 0;if(x==y)return 1;if(dp[x][y]!=-1)return dp[x][y];int i, tmp=maxn, s;for(i=x; i<y; i++){if(solve(x, i)+solve(i+1, y)<tmp){tmp=solve(x, i)+solve(i+1, y);s=i;}}if(match(x, y)&&solve(x+1, y-1)<tmp){tmp=solve(x+1, y-1);s=-1;}dp[x][y]=tmp;flag[x][y]=s;return tmp;
}void solve2(int x, int y){if(x>y)return ;if(x==y){getmatch(x);return ;}if(flag[x][y]==-1){printf("%c", str[x]);solve2(x+1, y-1);printf("%c", str[y]);}else {solve2(x, flag[x][y]);solve2(flag[x][y]+1, y);}
}int main(){scanf("%s", str);memset(dp, -1, sizeof(dp));len=strlen(str);solve(0, len-1);solve2(0, len-1);printf("\n");return 0;
}

 

这篇关于poj 1141 Brackets Sequence 括号匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---