[diary of supplementary questions] [2022 Niuke summer multi school 2] k-link with bracket sequence I

Pro

https://ac.nowcoder.com/acm/contest/33187/K

Sol

Code references std Writing , Because I really can't write dp, The topic is also a sentence too

With $f_{i,j,k}$ Represents a sequence b Before i Bit and sequence a Of LCS The length is k, And the number of left parentheses minus the number of right parentheses is j Number of alternatives .

The state transition equation can be easily seen in the following program , But it may not be easy to understand

Why do we have to else, Can't you put it directly in another bracket ？ We go through k You can see the value range of ,if Judge whether it is left and right brackets , The whole of its judgment str Sequence and the empty part after it , So if this is not left （ Right ） In parentheses , It may have been “a The sequence is b The subsequence ” Conditions considered , namely a Sequence traversal completed , Then it is not left （ Right ） Brackets . The state transition equation based on this case , here LCS The length of is still k, Therefore, the third dimension is k, You can also get the second dimension according to the left and right brackets （ Left parenthesis - Right bracket ） Update relationship （ Add one or subtract one ）.

In addition, there is another situation , namely a The sequence has not been traversed , At this time, consider that the next character is the left bracket or the right bracket , Similarly, consider adding one minus one according to the relationship between the left and right brackets , as well as LCS The change in length .

Questions about subscripts ： Subscript plus is used in many places in the following code 1 The way , Because the loop is from 0 At the beginning , To prevent the subscript from crossing the border , And a closer look reveals ： The first dimension is made up of i to update i+1 Value , This is in line with our routine dp; The second dimension is j to update j-1 perhaps j to update j+1, This is because there is no linear relationship between the difference between the number of left and right parentheses and the cycle of the first dimension , Therefore, the second dimension can only be updated according to whether it is the left bracket or the right bracket ; The third dimension has k to update k and k to update k+1 Two cases , As mentioned above , The two cases correspond to a The sequence has been traversed and a There are two cases when the sequence has not been traversed . As for subscript plus 1, Because it simplifies the processing of the beginning and avoids the case of negative subscripts .

Code

//By cls1277
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define endl '\n'

const LL maxn = 205;
const LL mod = 1e9+7;
LL f[maxn][maxn][maxn];

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef DEBUG
    freopen("data.txt","r",stdin);
    #endif
    LL t; cin>>t;
    while(t--) {
    
        LL n, m; cin>>n>>m;
        // string str; cin>>(str+1);
        char str[maxn]; cin>>(str+1);
        if(m&1) {
    
            cout<<0<<endl;
            continue;
        }
        Ms(f, 0);
        f[0][0][0] = 1;
        Fo(i,0,m-1) {
    
            Fo(j,0,i) {
     //left-right
                Fo(k,0,i) {
     //lcs
                	if(j) {
    
                		if(str[k+1]==')') f[i+1][j-1][k+1]=(f[i+1][j-1][k+1]+f[i][j][k])%mod;
                		else f[i+1][j-1][k] = (f[i+1][j-1][k]+f[i][j][k])%mod;
					}
					if(str[k+1]=='(') f[i+1][j+1][k+1] = (f[i+1][j+1][k+1]+f[i][j][k])%mod;
					else f[i+1][j+1][k] = (f[i+1][j+1][k]+f[i][j][k])%mod;
                }
            }
        }
        cout<<f[m][0][n]<<endl;
    }
    return 0;
}