首页 > 代码库 > topcoder srm 686 div1 -3
topcoder srm 686 div1 -3
1、给出只包含‘(‘,‘)‘,‘[‘,‘]‘的字符串$s$，删除一些字符，使得剩下的是合法的括号。有多少种删除方法？ $|s|\leq 40$
思路：左括号和右括号较少的一种不会大于20。假设左括号少。设$f[i][mask][k]$表示处理了前$i$个字符，其中留下的字符以$k$开头（$k=0$表示‘(‘,$k=1$表示‘[‘），且所有留下的字符状态为$mask$，（$mask$的最高位为1，其他位为0表示另一种括号，否则表示跟最高位相同的符号）。
#include <stdio.h>#include <string.h>#include <string>#include <iostream>#include <vector>#include <set>#include <map>#include <queue>#include <algorithm>#include <stack>using namespace std;long long f[2][1<<20][2];class BracketSequenceDiv1{public: long long count(string s) { const int n=(int)s.size(); int L=0,R=0; for(int i=0;i<n;++i) { if(s[i]==‘(‘||s[i]==‘[‘) ++L; else ++R; } if(L>R) { reverse(s.begin(),s.end()); for(int i=0;i<n;++i) { if(s[i]==‘(‘) s[i]=‘)‘; else if(s[i]==‘)‘) s[i]=‘(‘; else if(s[i]==‘[‘) s[i]=‘]‘; else s[i]=‘[‘; } swap(L,R); } int pre=0,cur=1; memset(f[pre],0,sizeof(f[pre])); f[0][0][0]=1; for(int i=1;i<=n;++i) { char c=s[i-1]; memset(f[cur],0,sizeof(f[cur])); for(int j=0;j<(1<<L);++j) for(int k=0;k<2;++k) if(f[pre][j][k]) { long long p=f[pre][j][k]; f[cur][j][k]+=p; if(c==‘(‘) { if(j==0) f[cur][1][0]+=p; else f[cur][j<<1|(!k)][k]+=p; } else if(c==‘[‘) { if(j==0) f[cur][1][1]+=p; else f[cur][j<<1|k][k]+=p; } else if(c==‘)‘) { if(j!=0&&(k^(j&1))) f[cur][j>>1][k]+=p; } else { if(j!=0&&(0==(k^(j&1)))) f[cur][j>>1][k]+=p; } } pre^=1; cur^=1; } return f[pre][0][0]+f[pre][0][1]-1; }};
topcoder srm 686 div1 -3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。