“蔚來杯“2022牛客暑期多校訓練營2 K.[Link with Bracket Sequence I] 括号序列 DP

K.​​Link with Bracket Sequence I​​ (DP)

題目分析

給定長度為的括号序列(不保證合法性)，求在此基礎上生成的長度為括号序列的方案數。

設表示插入括号的數量為、使用的原來的序列中的括号數量為，左括号比右括号多時的方案數。那麼最終答案為。那麼考慮如何設計狀态轉移：

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#pragma g++ optimize(2)
// #define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, mod = 1e9 + 7;
int dp[220][220][220];

inline void solve(){
    // memset(dp, 0, sizeof(dp));
    int m, n; cin >> n >> m;
    string s; cin >> s;
    // if(n & 1 || (m - n) & 1) { cout << 0 << endl; return; }
    dp[0][0][0]=1;
    for (int i = 0; i <= m - n; ++i)
    for (int j = 0; j <= n; ++j)
        for (int k = 0; k <= m; ++k){
            if (s[j] == '(' && j < n)
                dp[i][j + 1][k + 1] = (dp[i][j + 1][k + 1] + dp[i][j][k]) % mod;
            else
                dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % mod;
            if (k > 0){
                if (s[j] == ')' && j < n)
                    dp[i][j + 1][k - 1] = (dp[i][j + 1][k - 1] + dp[i][j][k]) % mod;
                else
                    dp[i + 1][j][k - 1] = (dp[i + 1][j][k - 1] + dp[i][j][k]) % mod;
            }
        }
    cout << dp[m - n][n][0] << endl;
    for(int i = 0; i <= m + 2; i++)
        for(int j = 0; j <= n + 2; j++)
            for(int k = 0; k <= m + 2; k++) dp[i][j][k] = 0;
}

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