2022 Niuke summer multi school K - link with bracket sequence I (linear DP)

The question ：

It is known that Bracket sequence a yes One The length is m Of Legal bracket sequence b Of Subsequence , seek Possible sequences b The number of .（ Be careful , Subsequences can be discontinuous ）

Ideas ：

State means ：dp[i][j][k] Express In the sequence b Before i In a ,a Before j Characters Included in b in , And Left parenthesis Than Right bracket many j Number of projects

According to the state representation , The final answer is ：dp[m][n][0]
（ This is also the first point that should be clear ： When a sequence of parentheses is a legal sequence , To meet the Left 、 The number of right parentheses should be equal This condition , But this condition is obviously not a sufficient and necessary condition ）

specific working means ：（ State shift ）

We Each enumeration sequence b pass the civil examinations i Possible cases of characters , And its Is it in the sequence a Of lcs Sequence （ Longest common subsequence ） in , So there will be Four situations , Discuss... Separately ：

• Case one ： Sequence a Of the j The characters are （, And b Of the i Characters and a Of the j Characters form lcs Sequence , So there are dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-1][k-1]) % mod, in other words b The first of the sequence i Characters are also （, that stay b Before i - 1 Of the characters Left parenthesis Than Right bracket number many k - 1 individual , and The previous state Of The longest matching length is j - 1

• The second case ： Sequence a Of the j The characters are ）, And b Of the i Characters and a Of the j Characters form lcs Sequence , So there are dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-1][k+1]) % mod, in other words b The first of the sequence i Characters are also ）, that stay b Before i - 1 Of the characters Left parenthesis Than Right bracket number many k + 1 individual , and The previous state Of The longest matching length is j - 1

• The third case ： Current position （, however Not with a Sequence number j Match parentheses in positions , Then there is dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k-1]) % mod, because The current position is （, therefore stay b Before i - 1 Of the characters Left parenthesis Than Right bracket number many k - 1 individual , And a The number of sequence matches does not change

• The fourth situation ： Current position ）, however Not with a Sequence number j Match parentheses in positions , Then there is dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k+1]) % mod, because The current position is ）, therefore stay b Before i - 1 Of the characters Left parenthesis Than Right bracket number many k + 1 individual , And a The number of sequence matches does not change

One thing to pay attention to is the boundary problem , In the process of dynamic transfer, you cannot index the array with negative numbers .

Code ：

#include <bits/stdc++.h>

using namespace std;
//#define map unordered_map
//#define int long long
int n;
const int N = 210, mod = 1e9 + 7;
char a[N];
int dp[N][N][N];

signed main()
{
    
	int T; cin >> T;
	while (T--)
	{
    
		int n, m; scanf("%d%d", &n, &m);
		scanf("%s", a + 1);
		memset(dp, 0, sizeof dp);
		dp[0][0][0] = 1;
		for (int i = 1; i <= m; ++i)
		{
    
			for (int j = 0; j <= min(n, i); ++j)
			{
    
				for (int k = 0; k <= m; ++k)
				{
    
					// branch 4 In this case 
					if (j >= 1 && k >= 1 && a[j] == '(') {
    // discharge  ( 
						dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][k - 1]) % mod;
					}
						
					if (j >= 1 && a[j] == ')') {
    // discharge  )
						dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][k + 1]) % mod;
					}
						
					if (k >= 1 && (j == 0 || a[j] == ')')) {
    // discharge  (
						dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % mod;
					}
						
					if (j == 0 || a[j] == '(') {
    // discharge  )
						dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k + 1]) % mod;
					}	
				}
			}
		}
			
		printf("%lld\n", dp[m][n][0]);
	}
	return 0;

}