跳转至

牛客多校2 K

题目链接

题目大意

给出括号序列\(s\)，求出长度为\(m\)能变成\(s\)的合法括号序列\(p\)的个数

题解

本题实际是求最长公共子序列是\(s\)的方案数，考虑DP，令\(f[i,j,k]\)表示前\(i\)个字符中与原串s的最长公共子序列为\(j\)的序列，且左括号数量比右括号多\(k\)个的方案数，状态转移如下:

  • \(s[j+1]=左括号\)
    • 放左括号：\(f[i,j+1,k+1]=f[i,j+1,k+1]+f[i-1,j,k]\)
    • 放右括号：\(k \ge 1时,f[i,j,k - 1]=f[i,j,k-1]+f[i-1,j,k]\)
  • \(s[j+1]=右括号\)
    • 放左括号：\(f[i,j,k+1]=f[i,j,k+1]+f[i-1,j,k]\)
    • 放右括号：\(k\ge 1时,f[i,j+1,k-1]=f[i,j+1,k-1]+f[i-1,j,k]\)
  • \(s匹配完毕\)
    • 放左括号：\(f[i,j,k+1]=f[i,j,k+1]+f[i-1,j,k]\)
    • 放右括号：\(k\ge 1时,f[i,j,k-1]=f[i,j,k-1]+f[i-1,j,k]\)

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <cmath>

using namespace std;
typedef pair<int, int> PII;
const int N = 210 , INF = 0x3f3f3f3f, mod = 1e9 + 7;
int f[N][N][N];
int n, m, a[N];
string s;

void add(int& x, int v) {
    x += v;
    if (x >= mod) x -= mod;
}

void solve()
{
    cin >> n >> m >> s;
    s = " " + s; 
    memset(f, 0, sizeof f);
    f[0][0][0] = 1; 

    for(int i = 1 ; i <= m ; i ++ )
    {
        for(int j = 0 ; j <= n ; j ++ )
        {
            for(int k = 0 ; k <= m ; k ++ )
            {
                if(s[j + 1] == '(') // i位置放(
                {
                    f[i][j + 1][k + 1] = (f[i][j + 1][k + 1] + f[i - 1][j][k]) % mod ;
                    if(k) f[i][j][k - 1] = (f[i - 1][j][k] + f[i][j][k - 1]) % mod;
                }
                else if(s[j + 1] == ')') // i位置放)
                {
                    f[i][j][k + 1] = (f[i - 1][j][k] + f[i][j][k + 1]) % mod;
                    if(k) f[i][j + 1][k - 1] = (f[i - 1][j][k] + f[i][j + 1][k - 1]) % mod;
                }
                else // s串匹配完毕 但是长度不够
                {
                    f[i][j][k + 1] = (f[i][j][k + 1] + f[i - 1][j][k]) % mod;
                    if(k) f[i][j][k - 1] = (f[i][j][k - 1] + f[i - 1][j][k]) % mod;
                }
            }
        }
    }

    cout << f[m][n][0] << endl;
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int T = 1;
    cin >> T;
    while(T -- ) solve();
    return 0;
}