官方题解

题目大意

求长度为 $n$ 的括号序列 $a$ 可能是多少个长度为 $m$ 的合法括号序列 $b$ 的子序列。

题目思路

读题时需要注意的一个点是括号序列 $a$ 不一定是合法的，但求的括号序列 $b$ 一定是要合法的。

我们可以将 ( 看成权值为 $1$ ，将 ) 看成权值为 $-1$ ，那么一个合法的括号序列需要满足以下条件：

• 序列和为 $0$ 。
• 最小前缀和为不小于 $0$ 。

我们考虑用动态规划解决这个问题。

设 $dp_{i,j,k}$ 表示括号序列 $b$ 中已经有 $i$ 个字符，括号序列 $a$ 的前 $j$ 个字符是括号序列 $b$ 的子序列，括号序列 $b$ 的权值前缀和为 $k$ 。

那么有以下四种转移：

• $i+1$ 位置为 ( ，且 $j=n$ 或 $s_{j+1}\ne$ ( ，则 $dp_{i+1,j,k+1}+=dp_{i,j,k}$ 。
• $i+1$ 位置为 ( ，且 $j<n$ 且 $s_{j+1}=$ ( ，则 $dp_{i+1,j+1,k+1}+=dp_{i,j,k}$ 。
• $i+1$ 位置为 ) ，且 $j=n$ 或 $s_{j+1}\ne$ ) ，则 $dp_{i+1,j,k-1}+=dp_{i,j,k}$ 。
• $i+1$ 位置为 ) ，且 $j<n$ 且 $s_{j+1}=$ ) ，则 $dp_{i+1,j+1,k-1}+=dp_{i,j,k}$ 。

时间复杂度 $O(nm^2)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 310;
const int mod = 1e9+7;

int dp[N][N][N];

void solve(){
    int n,m;cin>>n>>m;
    string s;cin>>s;s=' '+s;
    for(int i=0;i<=m+1;i++){
        for(int j=0;j<=n+1;j++){
            for(int k=0;k<=m+1;k++){
                dp[i][j][k]=0;
            }
        }
    }
    
    dp[0][0][0]=1;
    for(int i=0;i<m;i++){
        for(int j=0;j<=min(i,n);j++){
            for(int k=0;k<=i;k++){
                if(!dp[i][j][k]) continue;
                
                if(k && (j==n || s[j+1]!=')')) (dp[i+1][j][k-1]+=dp[i][j][k])%=mod;
                if(k<m && (j==n || s[j+1]!='(')) (dp[i+1][j][k+1]+=dp[i][j][k])%=mod;
                if(k && j<n && s[j+1]==')') (dp[i+1][j+1][k-1]+=dp[i][j][k])%=mod;
                if(k<m && j<n && s[j+1]=='(') (dp[i+1][j+1][k+1]+=dp[i][j][k])%=mod;
            }
        }
    }
    cout<<dp[m][n][0]<<endl;
}

int main(){
    int T=1;cin>>T;
    while(T--){
        solve();
    }
}