做题记录整理dp13 P7914 [CSP-S 2021] 括号序列（2022/9/26）

P7914 [CSP-S 2021] 括号序列
非常考思维的思维题（甚至做到了让全广西都恐惧（似乎广西连拿暴力分的人都没有））
由于看了题解，所以这题相当于是在巨人的肩膀上做题了。。。
而且这位大佬的代码风格和我非常像，导致我打完发现和抄题解似的。。。

#include<bits/stdc++.h>
#define for1(i,a,b) for(ll i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
ll n,k,dp[505][505][10];
const ll md=1e9+7;
string s;
//0:形态如***...*的括号序列（即全部是*）。
// 1: 形态如(...)的括号序列（即左右直接被括号包裹且最左边括号与最右边的括号相互匹配）。
// 2: 形态如(...)**(...)***的括号序列（即左边以括号序列开头，右边以*结尾）。
// 3: 形态如(...)***(...)*(...)的括号序列（即左边以括号序列开头，右边以括号序列结尾，注意：第2种形态也属于这种形态）。
// 4: 形态如***(...)**(...)的括号序列（即左边以*开头，右边以括号序列结尾）。
// 5: 形态如***(...)**(...)**的括号序列（即左边以*开头，右边以*结尾，注意：第1种形态也属于这种形态）。
bool cl(ll a,ll b) 
{
     return (s[a]=='('||s[a]=='?')&&(s[b]==')'||s[b]=='?');
}
int main(){
    scanf("%d%d\n",&n,&k);
    getline(cin,s);
    s.insert(0," ");
    for1(i,1,n) dp[i][i-1][0]=1;
    for1(len,1,n)
        for1(l,1,n-len+1)
		{
            int r=l+len-1;
            
            if(len<=k) dp[l][r][0]=dp[l][r-1][0]&&(s[r]=='*'||s[r]=='?');
            
            if(len>=2)
			{
                if(cl(l,r)) dp[l][r][1]=(dp[l+1][r-1][0]+dp[l+1][r-1][2]+dp[l+1][r-1][3]+dp[l+1][r-1][4])%md;
                for1(i,l,r-1)
				{
                    dp[l][r][2]=(dp[l][r][2]+dp[l][i][3]*dp[i+1][r][0])%md;
                    dp[l][r][3]=(dp[l][r][3]+(dp[l][i][2]+dp[l][i][3])*dp[i+1][r][1])%md;
                    dp[l][r][4]=(dp[l][r][4]+(dp[l][i][4]+dp[l][i][5])*dp[i+1][r][1])%md;
                    dp[l][r][5]=(dp[l][r][5]+dp[l][i][4]*dp[i+1][r][0])%md;
                }
            }
			dp[l][r][3]=(dp[l][r][3]+dp[l][r][1])%md;
            dp[l][r][5]=(dp[l][r][5]+dp[l][r][0])%md;
        }
    printf("%lld\n",dp[1][n][3]);
    return 0;
}