2022多校第二场 K题 Link with Bracket Sequence I

题目链接

Link with Bracket Sequence I

题目大意

给定我们一个长度为$n$的括号序列，并且告诉我们它是一个长度为$m$的合法的括号序列的子串，问我们这个长度为$m$的括号序列有多少种情况？

题解

考虑DP，设$f_{i,j,k}$ 表示考虑$b$串的前i个字符，和$a$串的最长公共子序列长度为$j$，左括号比右括号多$k$，每次转移的时候枚举当前是左括号还是右括号，最后答案即为$f_{[m][n][0]}$。

代码

#include
#include
using namespace std;
const int maxn = 210;
const int mod = 1e9 + 7;
int f[maxn][maxn][maxn];
int main()
{
	int t; cin >> t;
	while(t --)
	{
		memset(f, 0, sizeof f);
		int n, m; 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 <= n && j <= i; j ++){
				for(int k = 0; k <= i; k ++){
					if(k) {
						if(j && s[j] == '(') f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][k - 1]) % mod;
						else f[i][j][k] = (f[i][j][k] + f[i - 1][j][k - 1]) % mod;
					}
					if(k != m) {
						if(!j || s[j] == '(') f[i][j][k] = (f[i][j][k] + f[i - 1][j][k + 1]) % mod;
						else f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][k + 1]) % mod;
					}
				}
			}
		}
		cout << f[m][n][0] << endl;
	}
}
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