区间DP

本体难度在于情况多,需要分类讨论且码量大
dp[i][j][k]表示区间i~j状态为k时的数量
其中维度k需要自己考虑清楚(本题难点)

#include<bits/stdc++.h>
using namespace std;
long long dp[510][510][6],n,k,mod=1000000007;
char s[510];
bool cmp(long long x,long long y){
    return (s[x]=='('&&s[y]==')'||s[x]=='('&&s[y]=='?'||s[x]=='?'&&s[y]==')'||s[x]=='?'&&s[y]=='?');
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        dp[i][i-1][0]=1;
    }
    for(int len=1;len<=n;len++){
        for(int l=1;l<=n-len+1;l++){
            int r=l+len-1;
            if(len<=k&&(s[r]=='*'||s[r]=='?'))dp[l][r][0]=dp[l][r-1][0] ;
            if(len>=2){
                if(cmp(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])%mod;
                for(int i=l;i<r;i++){
                    dp[l][r][2]=(dp[l][r][2]+dp[l][i][3]*dp[i+1][r][0])%mod;
                    dp[l][r][3]=(dp[l][r][3]+(dp[l][i][2]+dp[l][i][3])*dp[i+1][r][1])%mod;
                    dp[l][r][4]=(dp[l][r][4]+(dp[l][i][4]+dp[l][i][5])*dp[i+1][r][1])%mod;
                    dp[l][r][5]=(dp[l][r][5]+dp[l][i][4]*dp[i+1][r][0])%mod;
                }   
            }
            dp[l][r][5]=(dp[l][r][5]+dp[l][r][0])%mod;
            dp[l][r][3]=(dp[l][r][3]+dp[l][r][1])%mod;
        }
    }
    printf("%lld\n",dp[1][n][3]);
    return 0;
}

这个代码实际上还有优化维度的做法
可以自己思考思考