【2022牛客多校2 K Link with Bracket Sequence I】括号线性dp

题目链接

题面

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Link has a bracket sequence aa of length nn, which is a subsequence of a valid bracket sequence bb of length mm.

Link doesn’t remember bb, so he wonders the number of possible sequences bb.

A bracket sequence is valid if it satisfies any of the following conditions:
Its length is 00.
It can be represented as (A)(A), where AA is a valid bracket sequences.
It can be represented as ABAB, where AA and BB are both valid bracket sequence.

A sequence aa is a subsequence of a sequence bb if aa can be obtained from bb by deletion of several (possibly, zero or all) elements.
输入描述:
Each test contains multiple test cases. The first line contains the number of test cases TT (1 \le T \le 1001≤T≤100). Description of the test cases follows.

The first line contains two integers n,mn,m (1 \leq n \leq m \leq 2001≤n≤m≤200).

The second line contains a bracket sequence ss of length nn.

It is guaranteed that the sum of mm over all test cases does not exceed 10^310
3
.
输出描述:
For each test cases, output the number of possible sequences bb modulo 10^9+710
9
+7.

Note that the answer maybe 00 due to Link’s poor memory.
示例1
输入
3
2 2
()
2 4
)(
2 4
()
输出
1
1
2

题意：

对于每一个样例，给你一个n,m，和一个长度为n的字符串，现在需要构造出一个m个字符的字符串，给出的长度为n的字符串是你要构造出的子序列，问能构造出多少种合法并不同的括号序列

分析：

这个题就是dp，dp[i][j][k]表示要构造的序列的第i项，左括号的个数比右括号的个数大j，给出的串a和目前构造的串b的最长公共子序列是k的个数，其实这个转移的话就是有两种情况，一种是第i个位置放左括号，一种是右括号，这样dp就跑出来了，还有一点需要注意的就是那个取模的时候做减法比直接取模快一点，下面看代码

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
typedef long long LL;
LL f[402][202][202];
char s[444];
inline void add(LL &x,LL y){
    
	x += y;
	if(x >= mod) x -= mod;
}
void solve(){
    
	int n,m;
	cin>>n>>m>>(s+1);
	f[0][0][0] = 1;
	for(int i=1;i<=m;i++){
    
		for(int j=0;j<=m;j++){
    
			for(int k=0;k<=n;k++){
    
				{
    
					int nxk = k;
					if(s[k+1] == '(') nxk++;
					add(f[i][j+1][nxk],f[i-1][j][k]);
				}
				if(j >= 1){
    
					int nxk = k;
					if(s[k+1] == ')') nxk++;
					add(f[i][j-1][nxk],f[i-1][j][k]); 
				}
			}
		}
	}
	cout<<f[m][0][n]<<"\n";
	for(int i=1;i<=m;i++){
    
		for(int j=0;j<=m;j++){
    
			for(int k=0;k<=n;k++) f[i][j][k] = 0;
		}
	}
}
int main(){
    
	int _;
	cin>>_;
	while(_--) solve();
	return 0;
}