题目

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1e9+7;
int n,k,dp[515][515][16];
char s[515];
bool cp(int a,int b){
	return (s[a]=='('||s[a]=='?')&&(s[b]==')'||s[b]=='?');
}
signed main(){
	cin>>n>>k;
	scanf("%s",s+1);
	for(int i=1;i<=n;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){
				dp[l][r][0]=dp[l][r-1][0]&&(s[r]=='*'||s[r]=='?');
			}
			if(len>=2){
				if(cp(l,r)){
					dp[l][r][1]=(dp[l+1][r-1][0]+dp[l+1][r-1][1]+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-1;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",dp[1][n][3]);
	return 0;
} 

全WA。