ABC 312D题 Count Bracket Sequences

题意

• 给定一个非空的字符串，其由(,),?三个字符构成，其中?可以被(或者)给替换掉，求替换后的字符串是符合括号匹配的情况下的方案数。最后答案对mod=998244353取模

思路

1. 应该算是一个板题，一开始的想法是往卡特兰数的方向思考，但是可能是我太水了没想出来，然后一想到卡特兰数的dp求法，就顺理成章的想到了dp。
2. 我们将(替换成1，）替换成-1，对于一个合法的括号匹配来说，对于任何一项i,我们都有前缀和为正数，否则就不合法了。我们定义dp[i][j]为到达字符串的第i位，前缀和为j的情况下的方案数，那么我们就可以很容易得出状态转移方程:

• dp[i][j]=dp[i-1][j-1],（a[i]==1）
• dp[i][j]=dp[i-1][j+1]+dp[i-1][j-1],(a[i]==0)
• dp[i][j]=dp[i-1][j+1],(a[i]==-1)

3. 注意一下字符串的开头，当j==0时，防止数组越界，我们单独处理一下。当然注意取模，先取模后相加。

代码

string s;
cin>>s;
int n=s.length();
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
	if(s[i-1]=='(') a[i]=1;
	else if(s[i-1]==')') a[i]=-1;
	else a[i]=0;
}
for(int i=1;i<=n;i++)
{
	for(int j=0;j<=i;j++)
	{
		if(a[i]==1) dp[i][j]=dp[i-1][j-1]%mod;
		else if(a[i]==0)
		{
		    if(i==1&&j==0) dp[i][j]=0;
		    else dp[i][j]=(dp[i-1][j+1]%mod+dp[i-1][j-1]%mod)%mod;
		}
		else dp[i][j]=dp[i-1][j+1]%mod;
	}
}
cout<<dp[n][0]%mod<<endl;
return 0;

}