首页 > 代码库 > POJ 2955 Brackets(计数问题吗呵呵)
POJ 2955 Brackets(计数问题吗呵呵)
我只能说这道题和上一道动态规划的问题真的是太像了,连方法也一模一样
确实,计数也需要存状态,计数也是需要动规的。
此时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]); } } } int main() { while(scanf("%s",s)) { if(strcmp(s,"end")==0) break; memset(d,0,sizeof(s)); n = strlen(s); dp(); printf("%d\n",n-d[0][n-1]); } return 0; }然后用总的减去不规则的,就得到了最多的规则括号数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。