“蔚来杯“2022牛客暑期多校训练营2 K.[Link with Bracket Sequence I] 括号序列 DP

K.Link with Bracket Sequence I (DP) 题目分析

给定长度为 n n n的括号序列(不保证合法性)，求在此基础上生成的长度为 m m m括号序列的方案数。

设 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示插入括号的数量为 i i i、使用的原来的序列中的括号数量为 j j j，左括号比右括号多 k k k时的方案数。那么最终答案为 d p [ m − n ] [ n ] [ 0 ] dp[m - n][n][0] dp[m−n][n][0]。那么考虑如何设计状态转移：

首先枚举插入的括号数量，原来的括号序列和左括号比右括号多的数量。

如果目前枚举到的括号为左括号，并且使用的原括号的数量 < n 0 k>0，即左括号的数量大于右括号的数量，并且使用的原括号的数量 < n 0 k>0时，如果使用原序列括号的数目为 n n n，或当前枚举到左括号，则可以插入右括号： d p [ i + 1 ] [ j ] [ k − 1 ] = ( d p [ i + 1 ] [ j ] [ k − 1 ] + d p [ i ] [ j ] [ k ] ) % m o d dp[i + 1][j][k - 1] = (dp[i + 1][j][k - 1] + dp[i][j][k]) \% mod dp[i+1][j][k−1]=(dp[i+1][j][k−1]+dp[i][j][k])%mod

Code

#include 
#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