K-Link with Bracket Sequence I “蔚来杯“2022牛客暑期多校训练营2

K-Link with Bracket Sequence I

题目大意

一个长度为 $n$ 的括号序列 $a$ 是一个长度为 $m$ 的合法括号序列 $b$ 的子序列，给定 $a$，求可能的 $b$ 的数量($mod10^9+7$)。
其中合法括号序列为：

• 长度为 $0$
• 表示成($A$)，$A$ 为合法括号序列
• 表示成 $AB$，$A$ 和 $B$ 都是合法括号序列

数据范围：($1\le n\le m\le 200,T\le 100$)

题解

考虑 $dp$，dp[i][j][k] 表示前 $i$ 个最多匹配 $a$ 的前 $j$ 个，剩下 $k$ 个左括号未匹配的方案数。
状态转移：

1. $b$ 当前位放左括号
   if(a[j + 1] == '(') dp[i + 1][j + 1][k + 1] += dp[i][j][k]
else dp[i + 1][j][k + 1] += dp[i][j][k]
   放左括号未匹配数加一，如果与 $a$ 下一位相同那么匹配数加一。虽然可能可以与 $b$ 的后面匹配，当与前面匹配肯定比后面更优，这样也可以防止重复。
2. 同理当前位放右括号
   if(a[j + 1] == ')') dp[i + 1][j + 1][k - 1] += dp[i][j][k]
else dp[i + 1][j][k -1] += dp[i][j][k]
   注意此时 $k>0$，既之前必须有左括号，否则不合法。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 210;
const int mod = 1e9 + 7;

int dp[maxn][maxn][maxn]; // 前 i 个最多匹配 a 的前 j 个，剩下 k 个左括号未匹配
char s[maxn];

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return f * x;
}

int main() {
    int t = read();
    while(t--) {
        int n = read(), m = read();
        scanf("%s", s + 1);
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        for(int i = 0; i < m; i++)
            for(int j = 0; j <= n; j++)
                for(int k = 0; k <= i; k++) {
                    if(!dp[i][j][k]) continue;
                    int t = j + (s[j + 1] == '(');
                    dp[i + 1][t][k + 1] = (dp[i + 1][t][k + 1] + dp[i][j][k]) % mod;
                    t = j + (s[j + 1] == ')');
                    if(k) dp[i + 1][t][k - 1] = (dp[i + 1][t][k - 1] + dp[i][j][k]) % mod;
                }
        printf("%d\n", dp[m][n][0]);
    }
    return 0;
}