2022 Multi-school Second Session K Question Link with Bracket Sequence I

题目链接

Link with Bracket Sequence I

题目大意

Given us a length of $n$的括号序列,and tells us it is a length of $m$A substring of a valid parentheses sequence,Ask us that this length is$m$How many cases of parenthesis sequences are there？

题解

考虑DP,设$f_{i,j,k}$ 表示考虑$b$串的前i个字符,和$a$The longest common subsequence length of the string is $j$,左括号比右括号多$k$,Each time the enumeration is shifted, whether it is an opening or closing parenthesis,最后答案即为$f_{[m][n][0]}$.

代码

#include<iostream>
#include<cstring>
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;
	}
}