首页 > 代码库 > uva 1626 Brackets Sequence ?(动态规划)
uva 1626 Brackets Sequence ?(动态规划)
状态表示方法:d[ i ][ j ]表示的是一条序列的开始和结束;
状态定义:d[ i ][ j ]表示字串s[ i~j ] 需要添加的数量。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; char s[105]; int d[105][105]; bool match(char ch1,char ch2) { if((ch1=='['&&ch2==']')||(ch1=='(')&&ch2==')') return true; return false; } void dp() { for(int i=0;i<n;i++) { d[i+1][i]=0; d[i][i]=1; } for(int i=n-2;i>=0;i--) { for(int j=i+1;j<n;j++) { d[i][j]=n; if(match(s[i],s[j])) d[i][j]=min(d[i][j],d[i+1][j-1]); for(int k=i;k<j;k++) d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]); } } } void print(int i,int j) { if(i > j) return; if(i == j) { if(s[i]=='('||s[j]==')') printf("()"); else printf("[]"); return; } int ans = d[i][j]; if(match(s[i],s[j])&&ans==d[i+1][j-1]) { printf("%c",s[i]); print(i+1,j-1); printf("%c",s[j]); return; } for(int k=i;k<j;k++) { if(ans==d[i][k]+d[k+1][j]) { print(i,k); print(k+1,j); return; } } } int main() { int t; scanf("%d",&t); getchar(); for(int kase=1;kase<=t;kase++) { gets(s); gets(s); n = strlen(s); if(n==0){ printf("\n"); if(kase!=t) printf("\n"); continue; } dp(); print(0,n-1); printf("\n"); if(kase!=t) printf("\n"); } return 0; }
对本题来说,这是一道关于括号匹配的题目。关于括号匹配的题目很多,又用栈来实现的,也有想这道题一样,要动规来记录状态实现的。
状态不好定义不好想,状态转移也不好定义不好想,但是,哪有那么多不好想呢。
不会就学不懂就研究,你学会了做过了不就记住了么
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。