K. Link with Bracket Sequence I dp

K
dp
好难

题意

已知括号序列 $a$ 是一个长度为 $m$ 的合法括号序列 $b$ 的子序列，求可能的序列 $b$ 的数量。$n,m\le 200,T\le 100,\sum m\le 2000$

思路

用 $dp[i][j][k]$ 表示长度为 $i$ ，与子序列的 $lcs$ 长度为 $j$ ，左括号比右括号多了 $k$ 个的序列数量。初始 $dp[0][0][0]=1$ ，答案即为 $dp[m][n][0]$ 。
对于每个长度 $i=1\to m$ 枚举 $i-1$ 时的情况。

代码

int dp[maxn][maxn][maxn];//i 1~m, j 1~n, k 0~i
//前i位中与子序列的lcs长度为j且左括号比右括号多k个的合法方案数
void solve() {
    
    cin >> n >> m;
    cin >> s;
    s = ' ' + s;
    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 <= n; j++) {
    
            for(int k = 0; k <= i; k++) {
    
            	if(s[j+1] == '(') dp[i][j+1][k+1] = (dp[i][j+1][k+1] + dp[i-1][j][k]) % P;
            	else dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][j][k]) % P;
                if(k) {
    
                	if(s[j+1] == ')') dp[i][j+1][k-1] = (dp[i][j+1][k-1] + dp[i-1][j][k]) % P;
                	else dp[i][j][k-1] = (dp[i][j][k-1] + dp[i-1][j][k]) % P;
                }
            }
        }
    }
     cout << dp[m][n][0] << endl;
}