(2022 Niuke multi School II) k-link with bracket sequence I (dynamic planning)

subject ：

  The sample input ：

3
2 2
()
2 4
)(
2 4
()

Sample output ：

1
1
2

The question ： Known parenthesis sequence a Is a length of m The legal bracket sequence of b The subsequence , Find the possible sequence b The number of .

analysis ：f[i][j][k] In sequence b Before i In a , Contains the sequence a Before j Characters , And there are more left parentheses than right parentheses k Number of projects

The final answer is obviously f[m][n][0]

Update method ：

We enumerate the sequence every time b pass the civil examinations i Possible cases of characters , And whether it participates in and sequence a Of lcs In sequence , So there are four situations , Let's discuss it separately .

Case one ： Sequence a Of the j The characters are （, And b Of the i Characters and a Of the j Characters make up lcs Sequence , So there are f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k-1])%mod, in other words b The first of the sequence i The characters are （, So before i-1 Of the characters （ The number is more than ） A large number k-1 individual , And the longest matching length of the previous state 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 make up lcs Sequence , So there are f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k+1])%mod, in other words b The first of the sequence i The characters are ）, So before i-1 Of the characters （ The number is more than ） A large number k+1 individual , And the longest matching length of the previous state is j-1

The third case ： Current position （, however a The first of the sequence j The characters are ）, So I can't relate to a Sequence number j Match two locations , Then there is f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1])%mod, Because the current location is （, So before i-1 A position in the （ The number is more than ） A large number k-1 individual , And a The number of sequence matches does not change

The fourth situation ： Current position ）, however a The first of the sequence j The characters are （, So I can't relate to a Sequence number j Match two locations , Then there is f[i][j][k]=(f[i][j][k]+f[i-1][j][k+1])%mod, Because the current location is ）, So before i-1 A position in the （ The number is more than ） A large number 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 .

Here is the code ：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
const int N=203,mod=1e9+7;
typedef long long ll;
char s[N];
ll f[N][N][N];
//f[i][j][k] In sequence b Before i In a , Contains the sequence a Before j Characters , And there are more left parentheses than right parentheses k Number of projects 
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		scanf("%s",s+1);
		for(int i=0;i<=m;i++)
		for(int j=0;j<=n;j++)
		for(int k=0;k<=m;k++)
			f[i][j][k]=0;
		f[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++)
		{
			// Current position  ( 
			if(j>=1&&s[j]=='('&&k>=1)
				f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k-1])%mod;
			// Current position  )
			else if(j>=1&&s[j]==')')
				f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k+1])%mod;
			// Current position  (
			if(k>=1&&(j==0||s[j]==')'))
				f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1])%mod;
			// Current position  )
			if(j==0||s[j]=='(')
				f[i][j][k]=(f[i][j][k]+f[i-1][j][k+1])%mod;
		}
		printf("%lld\n",f[m][n][0]);
	}
	return 0;
}