(2022牛客多校二)K-Link with Bracket Sequence I（动态规划）

题目：

 样例输入：

3
2 2
()
2 4
)(
2 4
()

样例输出：

1
1
2

题意：已知括号序列a是一个长度为m的合法括号序列b的子序列，求可能的序列b的数量。

分析：f[i][j][k]表示在序列b的前i位中，包含序列a的前j个字符，且左括号比右括号多k个的方案数

最后的答案显然是f[m][n][0]

更新方法：

我们每次枚举序列b中第i个字符的可能情况，以及其是否参与到与序列a的lcs序列中，所以就会有四种情况，我们分别讨论一下就行.

第一种情况：序列a的第j个字符是（，且b的第i个字符和a的第j个字符组成lcs序列，那么有f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k-1])%mod,也就是说b序列的第i个字符是（，那么前i-1个字符中（数目就比）数目多k-1个，而且前一个状态的最长匹配长度是j-1

第二种情况：序列a的第j个字符是），且b的第i个字符和a的第j个字符组成lcs序列，那么有f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k+1])%mod，也就是说b序列的第i个字符是），那么前i-1个字符中（数目就比）数目多k+1个，而且前一个状态的最长匹配长度是j-1

第三种情况：当前位置放（，但是a序列的第j个字符是），所以无法与a序列第j个位置进行匹配，那么就有f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1])%mod，因为当前位置是（，所以前i-1个位置中（数目就比）数目多k-1个，与a序列匹配数目不变

第四种情况：当前位置放），但是a序列的第j个字符是（，所以无法与a序列第j个位置进行匹配，那么就有f[i][j][k]=(f[i][j][k]+f[i-1][j][k+1])%mod，因为当前位置是），所以前i-1个位置中（数目就比）数目多k+1个，与a序列匹配数目不变

需要注意的一点就是边界问题，在动态转移过程中不能出现用负数对数组进行索引的情况。

下面是代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
const int N=203,mod=1e9+7;
typedef long long ll;
char s[N];
ll f[N][N][N];
//f[i][j][k]表示在序列b的前i位中，包含序列a的前j个字符，且左括号比右括号多k个的方案数
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		scanf("%s",s+1);
		for(int i=0;i<=m;i++)
		for(int j=0;j<=n;j++)
		for(int k=0;k<=m;k++)
			f[i][j][k]=0;
		f[0][0][0]=1;
		for(int i=1;i<=m;i++)
		for(int j=0;j<=min(n,i);j++)
		for(int k=0;k<=m;k++)
		{
			//当前位置放 ( 
			if(j>=1&&s[j]=='('&&k>=1)
				f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k-1])%mod;
			//当前位置放 )
			else if(j>=1&&s[j]==')')
				f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k+1])%mod;
			//当前位置放 (
			if(k>=1&&(j==0||s[j]==')'))
				f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1])%mod;
			//当前位置放 )
			if(j==0||s[j]=='(')
				f[i][j][k]=(f[i][j][k]+f[i-1][j][k+1])%mod;
		}
		printf("%lld\n",f[m][n][0]);
	}
	return 0;
}