2022牛客暑假第二场

K-Link with Bracket Sequence I

题目链接

题意简述

给定长度为$nn$的括号序列a，求有多少种不同的有效括号序列b，其中b序列长度为$mm$，且满足a是b的子序列。 答案对$\ast 1e9+7\ast *1e9+7*$取模。

数据取值范围：$1\le n\le m\le 2001\; \backslash leq\; n\; \backslash leq\; m\; \backslash leq\; 200$ 。

题目分析

有效括号序列即为左右括号可以不遗漏、不重复地互相匹配的括号序列。那么，在不考虑子序列的情况下，如何求出构造一串有效括号序列的方案数呢？

——经典括号匹配——

首先，我们可以暴力出奇迹。暴力搜索显然是可行的，但是它的效率太低了。

那么，我们类似从排列组合考虑方案操作的角度去思考一下~~（其实是动态规划）~~：

当我们考虑从左到右，一个括号一个括号地去构造一个括号序列时，显然每一步只有两种选择：放左括号，和放右括号。

要使得括号序列合法，我们在选择括号的时候有一些需要注意的：

①第一个括号不能是右括号，否则它的左边不可能有左括号和它匹配；

②由于合法括号序列删掉一个合法的括号串后，剩下的序列仍然是合法序列，那么当括号序列已经是有效合法的，和①同理不能选择右括号。

如果我们使用一个变量$ii$记录当前括号序列的长度，一个变量$jj$记录当前的合法性（用当前有多少个未匹配的左括号/或者说当前需要多少右括号才能达成匹配）

那么，当我们在第$ii$个序列位置上放入左括号，那么未匹配的左括号数量就多了1，也就是说它的合法性$j_{a}j\_a$就是当括号序列长度是$i-1i-1$时的$j_b+1j\_b+1$。也即有$j_b=j_a-1j\_b=j\_a-1$。

同理，在第i个序列位置放入右括号有$j_b=j_a+1j\_b=j\_a+1$。

到这里，我们可以构造一个$dpdp$函数，表达在$i\mathrm{，}ji，j$这个状态下的方案总数。

那么当前状态的方案总数即是加入左或右两种选择之前的方案总数的和。

那么状态转移方程有：

$dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];$ (左括号+右括号）

——加入子序列的考虑——

那么加入一个给定的子序列的要求，又要如何构造这个序列呢？

首先很正常的，也许你和我们一样考虑过从总方案中扣除固定序列造成的影响，或者把给定的序列补全再考虑在其中插入规则的串，以及其他类似的考虑。

但这些都有一个非常麻烦的问题：去重。

子序列并不是连续的子串，序列中的字符可以在母序列任意位置。这让以上的考虑会出现大量的重复序列。这让这样的方案变得非常没有价值，甚至可能是无解的。

但同样由于子序列这种不连续的性质，我们可以把它当作构造材料使用。

也就是在加入左括号的时候，如果子序列的当前符号也是左括号，就把它当材料使用，右括号同理。把子序列的符号按顺序全部用完，构造出来的序列自然就满足包含这个子序列的条件了。

而回看题目的数据范围，显然它是支持我们跑一个三维dp的。

那么我们不妨加入一个维度参数k，表示当前已经使用了子序列的前k个字符。

——三维dp方案——

回到我们放置左右括号的角度。同时加上对当前子序列字其次

也就是：

$dp[i][j][k]+=dp[i-1][j-1][k-1]dp[i][j][k]+=dp[i-1][j-1][k-1]$;（左括号+消耗） ①

$dp[i][j][k]+=dp[i-1][j-1][k]dp[i][j][k]+=dp[i-1][j-1][k]$;（左括号+不消耗） ②

右括号同理：

$dp[i][j][k]+=dp[i-1][j+1][k-1]dp[i][j][k]+=dp[i-1][j+1][k-1]$;（右括号+消耗） ③

$dp[i][j][k]+=dp[i-1][j+1][k]dp[i][j][k]+=dp[i-1][j+1][k]$;（右括号+不消耗） ④

由于是否消耗判断的是子序列当前的括号类型，出于编写方便，我们把序列现在是左括号的①④和是右括号的②③写在一起。

——临界值考虑——

首先，由于规定了0个字符也是一个合法的括号串，有$dp[0][0][0]=1dp[0][0][0]=1$;

其次，在不考虑0字符这个情况时，

① i（串长）的取值范围是$[1,m][1,m]$;

② j（合法性）取值范围是$[0,i][0,i]$;

③k（子串使用量）取值范围是$[0,min(n,i)];[0,min(n,i)];$

由此确定了循环中的变量取值范围，但出现了需要考虑的新问题：越界。

$jj$和$kk$取0显然都是有意义的，而转移方程中的$j-1j-1$和$k-1k-1$在它们等于$00$的时候会越界。

对于$jj$，处理起来相对容易得多，我们思考$j=0j=0$时的意义：它表示括号序列已经有效合法。而操作后序列合法，新加入的括号必定是右括号。在右括号的转移方程中，没有j-1的出现。只要在左括号的转移方程前加上$j\mathrm{\ne }0j\ne 0$的判断即可

但对于$kk$，当$k=0k=0$时，表示目前未使用子串的字符，这时候判断子串当前是左括号还是右括号毫无意义。处理方法大概有两种：①特殊判断：在判断左右括号之前，判断$k=0k=0$的情况并采用对应方程式；或者把四个转移方程分在四个条件判断里；②预处理：事先跑一次$dp[i][j][0]dp[i][j][0]$；转移方程同二维的经典括号匹配。在后续的循环中$kk$从$k=1k=1$开始即可。

这里我采用了第二种方案。

至此题目已完整分析，最后输出结果是$dp[m][n][0]dp[m][n][0]$。另外记得在编写代码时记得需要模。

完整代码

#include<iostream>
#include<string.h>
#define mod (int)(1e9+7)
using namespace std;
int f[205][205][205]={0};
int main(){
	int t;
	cin>>t;
	while(t--){
		memset(f,0,sizeof dp);
		int n,m;
		cin>>n>>m;
		string a;
		cin>>a;
		f[0][0][0]=1;
		for(int i=1;i<=m;i++){
			for(int k=0;k<=m;k++){
				if(k!=0)
				f[i][0][k] = (f[i][0][k] + f[i - 1][0][k - 1]) % mod;
				f[i][0][k] = (f[i][0][k] + f[i - 1][0][k + 1]) % mod;
			}
		}
		
		for(int i=1;i<=m;i++){
            for(int k =0;k<=m;k++){
                for (int j=1;j<=min(n,i);j++){
                	if(a[j-1]=='('){
                		if(k!=0)
                		f[i][j][k]=(f[i][j][k] +f[i-1][j-1][k-1])%mod;//( 
                		f[i][j][k] = (f[i][j][k] + f[i - 1][j][k + 1]) % mod;//) 
                	}
                         
                    else{
                    	if(k!=0)
                    	f[i][j][k] = (f[i][j][k] + f[i - 1][j][k - 1]) % mod;//(
                        f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][k + 1]) % mod;//)
                    }
                }
            }
        }
		cout<<f[m][n][0]<<'\n';
	}
	return 0;
}