題目傳送門

我的博客-歡迎光臨喵

曾經(jīng)有位大佬說過，計(jì)數(shù)類問題不是排列組合就是 dp。可是它看著不像排列組合，所以我們考慮 dp。又注意到 \(n \le 500\)，很適合 \(O(n^3)\) 的解法，所以我們考慮區(qū)間 dp。

我們發(fā)現(xiàn)它給了全問號(hào)的部分分，也就是沒有原本字符串里字符的限制了。先考慮這一檔部分分。

如果設(shè) \(dp_{l,r}\) 表示區(qū)間 \([l,r]\) 的方案的話，似乎不太能處理括號(hào)匹配和星號(hào)個(gè)數(shù)限制。所以我們?cè)黾右痪S記錄形態(tài)，如下：

• \(dp_{l,r,0}\) 表示 \([l,r]\) 區(qū)間全是 * 號(hào)的方案數(shù)，形如 ** ... *。

• \(dp_{l,r,1}\) 表示 \([l,r]\) 是一整個(gè)括號(hào)序列的方案數(shù)，形如 (...)。

• \(dp_{l,r,2}\) 表示 \([l,r]\) 左側(cè)是括號(hào)序列，右側(cè)是 * 號(hào)的方案數(shù)，形如 (...)(...) ** ... * (...) ****。

• \(dp_{l,r,3}\) 表示 \([l,r]\) 左側(cè)是括號(hào)序列，右側(cè)也是括號(hào)序列的方案數(shù) （包括形態(tài) 1 ） ，形如 (...)(...) *** (...) ** ... * (...)。

• \(dp_{l,r,4}\) 表示 \([l,r]\) 左側(cè)是 * 號(hào)，右側(cè)是括號(hào)序列的方案數(shù)，形如 **** (...)(...) ** ... * (...)。

• \(dp_{l,r,5}\) 表示 \([l,r]\) 左側(cè)右側(cè)都是 * 號(hào)的方案數(shù)。 （包括形態(tài) 0 ） 。形如 *** (...) * (...)(...) ** ... * (...) ****。

轉(zhuǎn)移方程式也很清晰了，如下：

我們解釋一下。首先，對(duì)于任何方案來說，都一定要避免把兩部分星號(hào)并起來，這樣無法保證個(gè)數(shù)限制。

對(duì)于形態(tài) 0 ，顯然只能是 \([l,r-1]\) 之后再跟一個(gè)星號(hào)吧……所以方案數(shù)不變。

對(duì)于形態(tài) 1 ，這里卡一下定義，括號(hào)可以形如 (S) 、 (A) 、 (SA) 、 (AS) ，但是不可以形如 (SAS)。（事實(shí)證明，你無法構(gòu)造出來這樣的合法串）。

至于為什么沒有 1 形態(tài)，因?yàn)?\([l+1,r-1]\) 的 3 形態(tài)包括了 1 形態(tài)的所有情況。

對(duì)于形態(tài) 2 ，枚舉末尾星號(hào)串的起點(diǎn)，剛才說到兩部分星號(hào)不能合并，而且這是起點(diǎn)，所以前面部分末尾肯定是個(gè)右括號(hào)。

而 2 形態(tài)以左括號(hào)開頭，所以前面也是以左括號(hào)開頭的，故前半部分是 3 形態(tài)的。

5 形態(tài)的轉(zhuǎn)移同 2。

至于3、4兩個(gè)形態(tài)，我們枚舉的是末尾的括號(hào)串的開頭，而括號(hào)串不用擔(dān)心星號(hào)合并的問題，故前面以星號(hào)或括號(hào)結(jié)尾皆可。

對(duì)于 3 形態(tài)，前半部分應(yīng)該以左括號(hào)開頭，所以前半段的形態(tài)是 2 或 3 皆可。同理 4 形態(tài)的前半段是 4 或 5 形態(tài)。

這個(gè)時(shí)候就有人要問了：那你星號(hào)串的一開始是個(gè)空串，你括號(hào)里面也可以是個(gè)空串，那你怎么處理空串的情況呢？

好問題！對(duì)于 1 ~ \(n\) 的每個(gè) \(i\) ，我們初始化令 \(dp_{i,i-1,0}=1\)，也就是把 \(i\) 位置的空串歸到了 0 形態(tài)里。道理也比較簡(jiǎn)單，因?yàn)楹ㄌ?hào)的串非空。

嘗試帶回剛才的推導(dǎo)式，我們發(fā)現(xiàn)這么賦初值竟然不會(huì)出問題！很巧妙，對(duì)不對(duì)？

這就是 s 里面全是問號(hào)的解決方案。如果 s 里有一些字符已經(jīng)確定了，我們?cè)谵D(zhuǎn)移 0,1 兩個(gè)形態(tài)時(shí)判斷是否合法即可。

其他形態(tài)倒是不用判斷，因?yàn)楫吘箽w根到底都是從小區(qū)間的 0,1 形態(tài)轉(zhuǎn)移而來的。

代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<48){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}

inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}

const int N=520;
const int mod=1e9+7;
int n,k,dp[N][N][6];
char s[N];

inline bool check(int l,int r){
	//判斷這兩個(gè)位置能否填(、)兩個(gè)括號(hào) 
	return ((s[l]=='?'||s[l]=='(')&&(s[r]=='?'||s[r]==')'));
}

signed main(){
	//0:**...*
	//1:(...)
	//2:(...)***(...)***
	//3:(...)***(...)***(...)
	//4:***(...)***(...)
	//5:***(...)*(...)(...)***
	n=read(),k=read();
	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+len-1<=n;l++){
			int r=l+len-1;
			if(len<=k){
				if(s[r]=='*'||s[r]=='?'){//判斷r位置能不能填 * 
					dp[l][r][0]=dp[l][r-1][0];
				}
			}
			if(len>=2&&check(l,r)){
				dp[l][r][1]=(dp[l+1][r-1][0]+dp[l+1][r-1][2]+dp[l+1][r-1][4]+dp[l+1][r-1][3])%mod;
				//括號(hào)串兩邊不能全是* 
			}
			for(int k=l;k<r;k++){
				dp[l][r][2]=(dp[l][r][2]+(dp[l][k][3]*dp[k+1][r][0])%mod)%mod;
				dp[l][r][3]=(dp[l][r][3]+(dp[l][k][2]+dp[l][k][3])%mod*dp[k+1][r][1]%mod)%mod;
				dp[l][r][4]=(dp[l][r][4]+(dp[l][k][4]+dp[l][k][5])%mod*dp[k+1][r][1]%mod)%mod;
				dp[l][r][5]=(dp[l][r][5]+(dp[l][k][4]*dp[k+1][r][0])%mod)%mod;
			}
			dp[l][r][3]=(dp[l][r][3]+dp[l][r][1])%mod;
			dp[l][r][5]=(dp[l][r][5]+dp[l][r][0])%mod;
			//最后不要忘了統(tǒng)計(jì)0、1形態(tài)方案數(shù) 
		}
	}
	int ans=dp[1][n][3];
	//最終合法的形態(tài)只有3 
	printf("%lld",ans);
	return 0;
}

參考資料：

1.洛谷題解

這篇題解寫的很明白，我是照著他這個(gè)寫的自己題解，大家有什么不理解的也可以看看這位大佬的題解OwO。