其实T2想清楚就不是很难，(虽然想清楚也不简单)
我这里分享一种很自然的想法，当然是区间dp啦
区间dp分6种状态
-
***的种类数，这种情况相当与题目中的
S
S
S，2到5中都一样
-
(...)的种类数，这种情况表示有括号包裹的合法序列，2到5中都一样
-
(...)***(...)***(...)***的种类数，表示以(...)开头，以***结尾的一长串，没有个数限制，比如(...)***也可以
-
(...)***(...)***(...)的种类数，表示以(...)开头，以(...)结尾的一长串，没有个数限制，比如(...)也可以
-
***(...)***(...)***(...)的种类数，表示以***开头，以(...)结尾的一长串，没有个数限制，比如***(...)也可以
-
***(...)***(...)***的种类数，表示以***开头，以***结尾的一长串，没有个数限制，比如***也可以
转移很自然：
d
p
[
l
]
[
r
]
[
0
]
=
(
r
−
l
+
1
≤
k
)
∗
d
p
[
l
]
[
r
−
1
]
[
0
]
∗
(
s
[
r
]
=
=
′
∗
′
∣
∣
s
[
r
]
=
=
′
?
′
)
dp[l][r][0]=(r-l+1\le k)*dp[l][r-1][0]*(s[r]=='*'||s[r]=='?')
dp[l][r][0]=(r−l+1≤k)∗dp[l][r−1][0]∗(s[r]==′∗′∣∣s[r]==′?′)
d
p
[
l
]
[
r
]
[
1
]
=
p
i
p
e
i
(
l
,
r
)
∗
(
d
p
[
l
+
1
]
[
r
−
1
]
[
2
]
+
d
p
[
l
+
1
]
[
r
−
1
]
[
3
]
+
d
p
[
l
+
1
]
[
r
−
1
]
[
4
]
)
dp[l][r][1]=pipei(l,r)*(dp[l+1][r-1][2]+dp[l+1][r-1][3]+dp[l+1][r-1][4])
dp[l][r][1]=pipei(l,r)∗(dp[l+1][r−1][2]+dp[l+1][r−1][3]+dp[l+1][r−1][4])
其中
p
i
p
e
i
(
l
,
r
)
pipei(l,r)
pipei(l,r)表示
s
[
l
]
s[l]
s[l]和
s
[
r
]
s[r]
s[r]可以匹配成括号
d
p
[
2
]
[
l
]
[
r
]
=
∑
d
p
[
3
]
[
l
]
[
i
]
∗
d
p
[
0
]
[
i
+
1
]
[
r
]
dp[2][l][r]=\sum dp[3][l][i]*dp[0][i+1][r]
dp[2][l][r]=∑dp[3][l][i]∗dp[0][i+1][r]
d
p
[
3
]
[
l
]
[
r
]
=
∑
(
d
p
[
2
]
[
l
]
[
i
]
+
d
p
[
3
]
[
l
]
[
i
]
)
∗
d
p
[
1
]
[
i
+
1
]
[
r
]
dp[3][l][r]=\sum (dp[2][l][i]+dp[3][l][i])*dp[1][i+1][r]
dp[3][l][r]=∑(dp[2][l][i]+dp[3][l][i])∗dp[1][i+1][r]
d
p
[
4
]
[
l
]
[
r
]
=
∑
(
d
p
[
5
]
[
l
]
[
i
]
+
d
p
[
4
]
[
l
]
[
i
]
)
∗
d
p
[
1
]
[
i
+
1
]
[
r
]
dp[4][l][r]=\sum (dp[5][l][i]+dp[4][l][i])*dp[1][i+1][r]
dp[4][l][r]=∑(dp[5][l][i]+dp[4][l][i])∗dp[1][i+1][r]
d
p
[
5
]
[
l
]
[
r
]
=
∑
d
p
[
4
]
[
l
]
[
i
]
∗
d
p
[
0
]
[
i
+
1
]
[
r
]
dp[5][l][r]=\sum dp[4][l][i]*dp[0][i+1][r]
dp[5][l][r]=∑dp[4][l][i]∗dp[0][i+1][r]
最后不要忘了把
d
p
[
l
]
[
r
]
[
0
]
dp[l][r][0]
dp[l][r][0]算到
d
p
[
l
]
[
r
]
[
5
]
dp[l][r][5]
dp[l][r][5]里，还有
d
p
[
l
]
[
r
]
[
1
]
dp[l][r][1]
dp[l][r][1]算到
d
p
[
l
]
[
r
]
[
3
]
dp[l][r][3]
dp[l][r][3]里，不知到为什么可以重新看一遍dp六种状态的定义
我的考场代码（不要学我#define int long long啊）：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=510,mod=1e9+7;
int n,k,dp[6][N][N];
char s[N];
bool pipei(int l,int r){
return (s[l]=='('||s[l]=='?')&(s[r]==')'||s[r]=='?');
}
signed main(){
freopen("bracket.in","r",stdin);
freopen("bracket.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k>>s+1;
for(int i=1;i<=n;i++)dp[0][i][i-1]=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)dp[0][l][r]=dp[0][l][r-1]&&(s[r]=='*'||s[r]=='?');
if(len>=2){
dp[1][l][r]=pipei(l,r)*(dp[2][l+1][r-1]+dp[3][l+1][r-1]+dp[4][l+1][r-1]+dp[0][l+1][r-1])%mod;
for(int i=l;i<r;i++){
(dp[2][l][r]+=dp[3][l][i]*dp[0][i+1][r])%=mod;
(dp[3][l][r]+=(dp[2][l][i]+dp[3][l][i])*dp[1][i+1][r])%=mod;
(dp[4][l][r]+=(dp[5][l][i]+dp[4][l][i])*dp[1][i+1][r])%=mod;
(dp[5][l][r]+=dp[4][l][i]*dp[0][i+1][r])%=mod;
}
}
(dp[5][l][r]+=dp[0][l][r])%=mod;
(dp[3][l][r]+=dp[1][l][r])%=mod;
}
}
cout<<dp[3][1][n];
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
