牛客33187K多校 - Link with Bracket Sequence I

• 链接：
• 知识点：DP、组合数学
• 难度：紫

UPD 后续 杭电多校对本题出了续集。“Link with Bracket Sequence II”

https://blog.nowcoder.net/n/3d5af4fe3b58455a976ee3e312279d19

UPD 类似题

https://blog.nowcoder.net/n/cca78595e55d4783ad5f78f9e058d20c

题意

给出一个长度为 $nn$ 的括号序列（也能不合法）$SS$，需要构造出一个长度为 $mm$ 的新的合法的括号序列 $TT$，满足 $SS$ 是 $TT$ 的子序列。

构造的方案数，答案对 $10^9+710^9+7$ 取模。

思路

考虑 DP。

考虑括号的匹配问题，至少有一个状态是左括号数量减右括号数量的差值。

设计本题 DP 状态的关键在于如何保证计数能够不重不漏。

考虑括号序列的形态，可以将括号序列 $TT$ 中连续相同的括号合成一个连通块，将 $TT$ 看成多个连通块的形式。不难发现，$TT$ 中连通块的数量 $\ge n\backslash geq\; n$。

我们只需要固定 $TT$ 的最后 $nn$ 个连通块和 $SS$ 中的 $nn$ 个字符一一匹配，前缀随便放即可。

实现

令 $f_{i,j,k}f\_\{i,j,k\}$ 表示：当前是 $TT$ 中的第 $ii$ 个字符，当前连通块和 $SS$ 中第 $jj$ 个字符匹配，当前左括号比右括号多 $kk$ 个。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#define int long long
const int N	= 210;
const int MOD	= 1e9+7;
using namespace std;

char str[N];
int dp[N][N][N];
int T,n,m;

void Sol()
{
	for (int i=0; i<=m; i++)
		for (int j=0; j<=n; j++)
			for (int k=0; k<=m; k++)
				dp[i][j][k] = 0;
			
	dp[0][0][0] = 1;
	for (int i=1; i<=m; i++)
	{
		for (int j=0; j<=i; j++)
		{
			dp[i][0][j] += (j-1<0?0:dp[i-1][0][j-1]) + dp[i-1][0][j+1], dp[i][0][j]%=MOD;
		}
	}
	
	for (int i=1; i<=m; i++)
	{
		for (int j=1; j<=min(m, n); j++)
		{
			for (int k=0; k<=i; k++)
			{
				int d = -1 + 2*(str[j]=='(');
				if(k-d>=0)	dp[i][j][k] += dp[i-1][j-1][k-d];
				if(k+d<=m)	dp[i][j][k] += dp[i-1][j][k+d];
				dp[i][j][k] %= MOD;
			}
		}
	}
	printf("%lld\n",dp[m][n][0]);
	
}

signed main()
{
	scanf("%lld",&T);
	while (T--)
	{
		scanf("%lld %lld",&n,&m);
		scanf("%s",str+1);
		Sol();
	}
	
	return 0;
}