Link with Bracket Sequence I（状态基多维dp）

"蔚来杯"2022牛客暑期多校训练营2

Problem

给定一个长度为n的括号序列a，问：构成长度为m（$n\le m$）的合法括号序列b有多少种方案。

Solution

$f[i][j][k]:表示长度为i的序列b包含a的前j个，且还有k个左括号还没有匹配的方案数$

• $a[j]={}^{\prime }{(}^{\prime }$
  当 $b[i]={}^{\prime }{(}^{\prime }f[i-1][j-1][k-1]\to f[i][j][k]$
  当 $b[i]={}^{\prime }{)}^{\prime }f[i-1][j][k+1]\to f[i][j][k]$
• $a[j]={}^{\prime }{)}^{\prime }$
  当 $b[i]={}^{\prime }{(}^{\prime }f[i-1][j][k-1]\to f[i][j][k]$
  当 $b[i]={}^{\prime }{)}^{\prime }f[i-1][j-1][k+1]\to f[i][j][k]$

Code

int n, m;
ll f[202][202][202];

int main()
{
	IOS;
	int T; cin >> T;
	while (T--)
	{
		cin >> n >> m;
		string s; cin >> s;
		s = " " + s;

		f[0][0][0] = 1;
		for(int i = 1; i <= m; i++)
			for(int j = 0; j <= min(i, n); j++)
				for (int k = 0; k <= i; k++)
				{
					f[i][j][k] = 0;
					if (j == 0)
					{
						if(k) f[i][j][k] += f[i - 1][j][k - 1];//第i位为左括号
						f[i][j][k] += f[i - 1][j][k + 1];//第i位为右括号
					}
					else if (s[j] == '(')
					{
						if(j && k) f[i][j][k] += f[i - 1][j - 1][k - 1];//第i位为左括号
						f[i][j][k] += f[i - 1][j][k + 1];//第i位为右括号
					}
					else
					{
						if(k) f[i][j][k] += f[i - 1][j][k - 1];//第i位为左括号
						if(j) f[i][j][k] += f[i - 1][j - 1][k + 1];//第i位为右括号
					}
					f[i][j][k] %= mod;
				}

		cout << f[m][n][0] << endl;
	}


	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43