首页 > 代码库 > UVa 1626 Brackets sequence (动态规划)
UVa 1626 Brackets sequence (动态规划)
题意：用最少的括号将给定的字符串匹配，输出最优解。可能有空行。
思路：dp。
dp[i][j]表示将区间i，j之间的字符串匹配需要的最少括号数，那么
如果区间左边是(或[，表示可以和右边的字符串匹配，枚举中间断点k，如果str[i]==str[k]则dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k+1][j])表示不需要加入新的括号，也可以插入新的括号则dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+1)。
如果区间最左边字符是）或]，那么它不可能和右边字符串匹配，状态转移为dp[i][j]=min(dp[i][j],dp[i+1][j]+1)
每次转移的时候记录一下转移路径，最后dfs输出即可。
注意可能有空串，所以要用gets。但是在题中每行读入之间有空行，所以要多用一个gets来吃掉这个空行，否则会出错。
建议交UVa，数据比较强。POJ和ZOJ数据较弱，我最初的代码在POJ和ZOJ都过了，UVa却一直TLE。
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<iostream>#define INF 10000000#define LL long longusing namespace std;int f[105][105];int flag[105][105];int pos[105][105];bool vis[105][105];char str[105];int dp(int L,int R){ if(L>R) return 0; if(vis[L][R]) return f[L][R]; vis[L][R]=true; f[L][R]=INF; if(str[L]==‘(‘||str[L]==‘[‘) { for(int i=L; i<=R; ++i) { if((str[L]==‘(‘&&str[i]==‘)‘)||(str[L]==‘[‘&&str[i]==‘]‘)) { int sx=dp(L+1,i-1),sy=dp(i+1,R); if(f[L][R]>sx+sy) { f[L][R]=sx+sy; flag[L][R]=-1; pos[L][R]=i; } } int dx=dp(L+1,i),dy=dp(i+1,R); if(f[L][R]>dx+dy+1) { f[L][R]=dx+dy+1; flag[L][R]=1; pos[L][R]=i; } } } else { int sx=dp(L+1,R); if(f[L][R]>sx+1) { f[L][R]=sx+1; flag[L][R]=1; pos[L][R]=L; } } return f[L][R];}void output(int L,int R){ if(L<=R) { int p=pos[L][R]; if(flag[L][R]<0) { putchar(str[L]); output(L+1,p-1); putchar(str[p]); output(p+1,R); } else { if(str[L]==‘)‘||str[L]==‘]‘) { if(str[L]==‘)‘) putchar(‘(‘); else putchar(‘[‘); putchar(str[L]); output(L+1,R); } else { putchar(str[L]); output(L+1,p); if(str[L]==‘(‘) putchar(‘)‘); else putchar(‘]‘); output(p+1,R); } } }}int main(){ int T; scanf("%d",&T); getchar(); while(T--) { gets(str); gets(str); memset(vis,0,sizeof(vis)); int L=strlen(str); dp(0,L-1); output(0,L-1); putchar(‘\n‘); if(T) putchar(‘\n‘); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。