2022牛客多校2 K-Link with Bracket Sequence I

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

1
1
2

 题目大意：已知b是一个长度为m的合法括号序列，a是b的一个子序列，现在我们知道a的长度，问满足条件的b有多少种。

解题思路：动态规划的思想。

状态表示：dp[i][j][k]表示b的前i个字符，和a的总共子序列长度为j，左括号比右括号多k个的情况。这样我们最终要求的答案就是dp[m][n][0]。

状态转移：对于当前的位置上括号的选择，可以选择左括号也可以选择右括号，此时与a序列匹配的对应的位置上也有两种情况，所以说我们当前的选择和a序列原有的字符各有两种可能，所以共有4种可能，因为对于同一种选择，由于a的原序列的不同会导致两种不同的状态表示。

上代码：

#include 
#include 
#include 
#include 
using namespace std;
const int N=210;
const int mod=1e9+7;
int dp[N][N][N],f[N][N][N];
int n,m;
char s[N];
void solve()
{
	cin>>n>>m>>s+1;
	memset(f,0,sizeof f);
	f[0][0][0]=1; 
	for(int i=0;i0)//当前位置选择右括号 
				{
					if(s[j+1]==')')
					f[i+1][j+1][k-1]=(f[i+1][j+1][k-1]+f[i][j][k])%mod;
					else
					f[i+1][j][k-1]=(f[i+1][j][k-1]+f[i][j][k])%mod; 
				}
				//当前位置选择左括号 
				if(s[j+1]=='(')
				f[i+1][j+1][k+1]=(f[i+1][j+1][k+1]+f[i][j][k])%mod;
				else
				f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k])%mod; 
				
			}
		cout<>t;
	while(t--)
	{
		solve();
	}
	return 0;
}