[2022 Niuke multi School Game 2] k-link with bracket sequence I

Feeling after the game

After this fight, I went to prison ,K The question was thought to be false , I was thinking about combinatorics + Searching violently but without success . I didn't expect it to be DP, I feel a little loss , After all, the essence of dynamic regression is combinatorics , Not then DP Come out and make up the question now . By the way, write blog Make a deep impression .
Original link

General idea of the question ：

Give a substring length and the original string length .
Another one Substring （A） , Let's ask how many Legal original string （B）.

Their thinking ：
DP thought ： Set before i individual B At most, it matches to the front j individual A , That is to ask how much is possible B Number of alternatives
At this time, you also need to pay attention to using only i j Of the tag dp Not necessarily legal , therefore dp Designed in three dimensions Design another K To judge whether it is legal , The judgment idea is yes K individual The left parenthesis is not matched ： Not zero , It's illegal .
State transition process ：

Now consider If in front of i individual B What happens if you put an open parenthesis after it

We get the transfer equation ：dp(i,j,k)->dp(i+1,j,k)
Think again , If A Of j+1 If it is a left parenthesis, it will match , If it's not, it can't match

If it is
dp(i,j,k)->dp(i+1,j+1,k+1)
If not
dp(i,j,k)->dp(i+1,j,k+1)
If it's right bracket I still need to see k Whether it is not zero , That is, there are unmatched left parentheses
AC Code ：

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define Buff std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 205;
const int mod = 1e9 + 7;
int t, n, m;
int dp[N][N][N];
signed main()
{
    
  Buff;
  cin >> t;
  
  while (t--)
  {
    
    cin >> n >> m;
    string s;
    cin >> s;
    s = " " + s;
    for (int i = 0; i <= m; i++)
      for (int j = 0; j <= n; j++)
        for (int k = 0; k <= i; k++) // k To i that will do 
        {
    
          dp[i][j][k] = 0;
        }
    dp[0][0][0] = 1; // initialization   There are no parentheses left in the empty sequence 
    for (int i = 0; i <= m; i++)
    {
    
      for (int j = 0; j <= n; j++)
      {
    
        for (int k = 0; k <= i; k++)
        {
    
          if (!dp[i][j][k])
            continue;
          if (s[j + 1] == '(')
            dp[i + 1][j + 1][k + 1] = (dp[i + 1][j + 1][k + 1] + dp[i][j][k]) % mod;// The derived state transition equation 
          else
            dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % mod;

          if (k)
            if (s[j + 1] == ')')
              dp[i + 1][j + 1][k - 1] = (dp[i + 1][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][0] << endl;
  }

  return 0;
}