Link with bracket sequence I (state based multidimensional DP)

" Weilai cup "2022 Niuke summer multi school training camp 2

Problem

Given a length of n The bracket sequence of a, ask ： The composition length is m（$n\le m$） The legal bracket sequence of b How many options are there .

Solution

$f[i][j][k]:The\; length\; isiSequencebcontainaBeforejindividual\; ,\; And\; there\; iskThere\; are\; no\; matching\; schemes\; in\; the\; left\; parenthesis$

• $a[j]={}^{\prime }{(}^{\prime }$
  When $b[i]={}^{\prime }{(}^{\prime }f[i-1][j-1][k-1]\to f[i][j][k]$
  When $b[i]={}^{\prime }{)}^{\prime }f[i-1][j][k+1]\to f[i][j][k]$
• $a[j]={}^{\prime }{)}^{\prime }$
  When $b[i]={}^{\prime }{(}^{\prime }f[i-1][j][k-1]\to f[i][j][k]$
  When $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];// The first i Bit is left parenthesis 
						f[i][j][k] += f[i - 1][j][k + 1];// The first i Bit is a right parenthesis 
					}
					else if (s[j] == '(')
					{
    
						if(j && k) f[i][j][k] += f[i - 1][j - 1][k - 1];// The first i Bit is left parenthesis 
						f[i][j][k] += f[i - 1][j][k + 1];// The first i Bit is a right parenthesis 
					}
					else
					{
    
						if(k) f[i][j][k] += f[i - 1][j][k - 1];// The first i Bit is left parenthesis 
						if(j) f[i][j][k] += f[i - 1][j - 1][k + 1];// The first i Bit is a right parenthesis 
					}
					f[i][j][k] %= mod;
				}

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


	return 0;
}