巅峰赛#25 T5

大部分思路在注释中
(本题中的n和m是以个人做题习惯而定，不是题目所给)
总体思路：用底劈进行处理（二维）
做题思路：我们可以从简单做起，先不判断是否存在该子序列，直接判断长度为n的字符串有多少种可能
当思考完以上时，题目就变得显然易见，因为这是子串并非子段，所以我们可以在列三维底劈进行处理，只要遇到合法就累加（因为与顺序无关）

AC code:

#include<bits/stdc++.h>
using namespace std;
//是我的错觉吗，感觉一串下来不在打表就在模拟（也可能是我思路氢气）
//观察题目，枚举逝世
//记忆化搜索肯定也得炸
//所以只能选择最最最‘简单’的算法，底劈
//观察数据范围“保证所有数据 m 的总和不超过 1e3”这提示我们应该向O(m^2)考虑🤔
//我有一计：关于括号的合法序列，那么当左边没有未匹配的左括弧时则不能添加右括弧
//注：答案%1e9+7，并且是加法，最多只会到2e9,不用开long long
int dp[310][310][310];//思考过后列出底劈，第i个位置有j个未被匹配的左括弧
//那么转移方程也很简单：dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
const int M=1e9+7;
int main(){
	int t;//喜闻乐见的无法骗分环节
    cin>>t;
    while(t--){
        memset(dp,0,sizeof dp);
    	int n,m;
        cin>>m>>n;
        string sm;//没有别的意思，只是长度为m的字符串子序列
        cin>>sm;
        if(n%2==1){
        	cout<<0<<'\n';
            continue;
        }
        //dp[1][1]=1;
    	//for(int i=2;i<=n;i++){
        	//for(int j=0;j<=min(i,n/2);j++){
            	//dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%M;
                //这里已经判断了不合法方案
            //}
        //}
        //long long ans=dp[n][0];
        //当最后一个位置未匹配左括弧为0时，才是方案数；
        //cout<<ans<<'\n';
        
        
        
        
        //到这里恭喜你写完了1%的输入输出，因为这只是判断总共合法方案数
        //但是你已经起码写完了一个基本模板，接下来这需要烧烤1145分钟即可在得出转移方程
        //题目该怎么写主要先看数剧范围，诶？每个序列都只有300，那么我们试着把dp改成三维
        //第i个位置有j个左括弧并且存在k个子序列中字符
     	dp[0][0][0]=1;
        for(int i=1;i<=n;i++){
        	sm+=' ';
        }//防越界
        int idx=0;
        //因为是子序列而并非连续子序列，所以遇到相同字符时直接累加即可
    	for(int i=0;i<=n;i++){
        	for(int j=0;j<=min(i,n/2+1);j++){
            	for(int k=0;k<=m;k++){//基本遍历(遍历已知点，求未知点)
                    if(dp[i][j][k]==0)continue;//如果都是0了还求啥啊
                    if(j<=(n/2)&&sm[k]=='(')//如果改点为左括弧
                        dp[i+1][j+1][k+1]=(dp[i+1][j+1][k+1]+dp[i][j][k])%M;
                    else
                        dp[i+1][j+1][k]=(dp[i+1][j+1][k]+dp[i][j][k])%M;
                    if(j>0&&sm[k]==')')//如果改点为右括弧
                        dp[i+1][j-1][k+1]=(dp[i+1][j-1][k+1]+dp[i][j][k])%M;
                    else
                        dp[i+1][j-1][k]=(dp[i+1][j-1][k]+dp[i][j][k])%M;
                }//该处遍历已知点，所以每次累加时要有边界判断
            }
        }
        int ans=dp[n][0][m];
        cout<<ans<<'\n';
    }
}