大佬教程收集整理的这篇文章主要介绍了CSP-S 2021 T2 括号序列 题解，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
考场上想了114514年不知道怎么避免算重。
看到 $ n leq 500 $ 就想到区间DP。设 $ f_{l,r,0/1/2/3} $ 表示方案数，0表示A，1表示SA，2表示AS，3表示SAS。并且设 $ s_{l,r} =sum_{i=0}^2 f_{l,r,i} $ 表示当 $ [l,r] $ 被括号括起来后是A的方案数。我们考虑怎么样统计答案来避免算重。
首先，如果 $ str_l = text{(} ,str_r = text{)} $ ，那么 $ f_{l,r,0} = s_{l+1,r-1} $ 。对于 $ f_{l,r,0/1} $ ，可以在右边最后一个(...)处统计答案；对于 $ f_{l,r,2} $ ，可以在左边最后一个(...)处统计答案；对于 $ f_{l,r,3} $ ，考虑在左边的S处统计答案。
想到怎么去重后就可以很好地DP了。
具体转移和一些边界情况见代码。
#include <bits/stdc++.h>
using namespace std;
inlinE int read(){
int f=1,r=0;char c=getchar();
while(!isdigit(C))f^=c=='-',c=getchar();
while(isdigit(C))r=(r<<1)+(r<<3)+(c&15),c=getchar();
return f?r:-r;
}
const int n=507,mod=1e9+7;
inline void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int n,K,f[n][n][4],s[n][n];
char str[n];
bool ok[n][n];
inline bool ck(int i,char C){return str[i]==c || str[i]=='?';}
inline bool brac(int i,int j){return ck(i,'(') && ck(j,')');}
int main(){
n=read(),K=read(),scanf("%s",str+1);
for(int i=1;i<=n;i++){
ok[i][i-1]=1;
for(int j=i;j<=min(i+K-1,n);j++)
ok[i][j]=ok[i][j-1]&ck(j,'*');
}
for(int i=1;i<n;i++)f[i][i+1][0]=brac(i,i+1),s[i][i+1]=ok[i][i+1]+brac(i,i+1);
for(int i=1;i<=n;i++)s[i][i-1]=1,s[i][i]=ok[i][i];
for(int len=3;len<=n;len++)
for(int l=1,r=len;r<=n;l++,r++){
if(brac(l,r))f[l][r][0]=s[l+1][r-1];
for(int k=l;k<r;k++){
if(brac(k+1,r)){
add(f[l][r][0],1ll*(f[l][k][0]+f[l][k][2])*s[k+2][r-1]%mod);
add(f[l][r][1],1ll*(f[l][k][1]+f[l][k][3]+ok[l][k])*s[k+2][r-1]%mod);
}
if(brac(l,k))add(f[l][r][2],1ll*s[l+1][k-1]*(f[k+1][r][2]+f[k+1][r][3]+ok[k+1][r])%mod);
if(ok[l][k])add(f[l][r][3],f[k+1][r][2]);
}
s[l][r]=ok[l][r];
for(int o=0;o<3;o++)add(s[l][r],f[l][r][o]);
}
printf("%dn",f[1][n][0]);
return 0;
}
以上是大佬教程为你收集整理的CSP-S 2021 T2 括号序列 题解全部内容，希望文章能够帮你解决CSP-S 2021 T2 括号序列 题解所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。