首页 > 代码库 > Bzoj4350 括号序列再战猪猪侠
Bzoj4350 括号序列再战猪猪侠
Submit: 97 Solved: 44
Description
括号序列与猪猪侠又大战了起来。
众所周知，括号序列是一个只有(和)组成的序列，我们称一个括号
序列S合法，当且仅当:
1.( )是一个合法的括号序列。
2.若A是合法的括号序列，则(A)是合法的括号序列。
3.若A，B是合法的括号序列，则AB是合法的括号序列。
我们考虑match[i]表示从左往右数第i个左括号所对应的是第几个右
括号，现在他得到了一个长度为2n的括号序列，给了你m个信息，第i
个信息形如ai,bi，表示match[ai]<match[bi]，要你还原这个序列。
但是你发现这个猪猪侠告诉你的信息，可能有多个括号序列合法；甚
至有可能告诉你一个不存在合法括号序列的信息！
你最近学了取模运算，你想知道答案对998244353(7*17*2^23+1)取
模的结果，这个模数是一个质数。
Input
第一行一个正整数T,T< = 5，表示数据组数。
对于每组数据，第一行一个n,m，n表示有几个左括号，m表示信息数。
接下来m行，每行两个数ai,bi，1< = ai,bi< = n。
Output
对于每组数据，输出一个数表示答案。
Sample Input
5
1 0
5 0
3 2
1 2
2 3
3 2
2 1
2 3
3 3
1 2
2 3
3 1
1 0
5 0
3 2
1 2
2 3
3 2
2 1
2 3
3 3
1 2
2 3
3 1
Sample Output
1
42
1
2
0
42
1
2
0
HINT
对于前两个点，是卡特兰数的情况。
对于第三个点，合法的情况只可能是 ()()()。
对于第四个点，合法情况可能是 (()()) 或者 (())()
对于第五个点，由于拓扑关系形成了环，显然无解。
对于 100% 的数据，保证 n < = 300
动态规划 区间DP 脑洞题
这两个家伙怎么打起来没完没了……
既然求方案数，那就愉快地DP吧。
考虑可能会有哪些情况：
只依据左括号进行决策，不表示出右括号，设f[i][j]为第i个到第j个左括号（和它们的右括号）构成的括号序列的方案数。
设last为一个已有的完整括号序列，新加入一对括号，可能有三种情况：
1、(last) 这要求从 i+1 到 j 范围内没有“右括号在 i 后面”的限制条件
2、()last 这要求从i+1 到 j 范围内没有 “右括号在 i 前面”的限制条件
3、( la ) st 枚举区间断点k，分别满足上面的条件
讨论三种情况进行转移即可。
注意特判有自环的情况。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int mod=998244353; 9 const int mxn=305;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14 return x*f;15 }16 int S[mxn][mxn],mp[mxn][mxn];17 int f[mxn][mxn];18 int n,m;19 void init(){20 memset(S,0,sizeof S);21 memset(mp,0,sizeof mp);22 memset(f,0,sizeof f);23 return;24 }25 int s(int x1,int y1,int x2,int y2){26 return S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1];27 }28 int main(){29 int i,j,u,v;30 int T=read();31 while(T--){32 init();33 n=read();m=read();34 bool flag=0;35 for(i=1;i<=m;i++){36 u=read();v=read();37 mp[u][v]=1;38 if(u==v)flag=1;39 }40 if(flag){puts("0");continue;}41 for(i=1;i<=n;i++)42 for(j=1;j<=n;j++)43 S[i][j]=S[i][j-1]+mp[i][j];44 for(i=1;i<=n;i++)45 for(j=1;j<=n;j++)46 S[i][j]+=S[i-1][j];47 //48 for(i=1;i<=n;i++)f[i][i]=1;49 for(int st=2;st<=n;st++){50 for(i=1;i+st-1<=n;i++){51 j=i+st-1;52 if(!s(i,i+1,i,j))f[i][j]=(f[i][j]+f[i+1][j])%mod;// ( last )53 if(!s(i+1,i,j,i))f[i][j]=(f[i][j]+f[i+1][j])%mod;// ()last54 for(int k=i+1;k<j;k++){ //(la)st55 if(!s(i,i+1,i,k) && !s(k+1,i,j,k)){56 f[i][j]=((LL)f[i][j]+(LL)f[i+1][k]*f[k+1][j]%mod)%mod;57 }58 }59 }60 }61 printf("%d\n",f[1][n]);62 }63 return 0;64 }
Bzoj4350 括号序列再战猪猪侠
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。