自动搬运

查看原文

来自洛谷，原作者为

	OccDreamer 百年如露

搬运于2025-08-24 22:19:46，当前版本为作者最后更新于2022-07-16 20:21:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

前置知识

区间型动态规划

思考过程

这题也算是一道很经典的问题了（？）。

看见 $n \leq 200$，不难想到复杂度为 $O(n^3)$ 的区间型动态规划。

题面中有这么一段话。

• 空串是规则括号序列。
• 如果 $\texttt A$ 是规则括号序列，那么 $\texttt{(A) [A] {A}}$ 都是规则括号序列。
• 如果 $\texttt A,\texttt B$ 都是规则括号序列，那个序列 $\texttt {AB}$ 也是规则括号序列。

这相当于直接告诉了我们动态规划的转移方程。

设 $dp(l,r)$ 表示由 $[l,r]$ 之间的字符组成的字符串有多少种不同的括号序列。

定义函数 $g(i,j)$ 表示第 $i$ 个字符与第 $j$ 个字符可以组成多少对不同的括号。

• 对于空串而言，令 $dp(l,l-1)=1$。
• 对于 $\texttt{(A)}$ 这一类的括号序列，可以写出转移方程 $dp(l,r)\leftarrow dp(l,r)+g(l,r)\times dp(l+1,r-1)$。
• 对于 $\texttt{AB}$ 类型的接下来我们重点讨论。

思路 $1$

我们能不能直接枚举一个位置 $p$，写出转移方程 $dp(l,r) \leftarrow dp(l,r) + \sum_{p=l+1}^{r-1} dp(l,p) \times dp(p+1,r)$。

经过思考不难发现这样是不行的，通过样例 $1$ 就可以发现。

如果按照上述思想，$dp(1,6)=dp(1,4) \times dp(5,6) +dp(1,2) \times dp(3,6)=2$，但是答案是 $1$。

这个转移错就错在重复计算了答案。

思路 $2$

沿用思路 $1$，既然知道问题出在哪，那么我们思考一下应该如何解决。

算重就是因为存在两个位置 $p_1,p_2$，满足 $[p_1,p_2]$ 构成合法的括号序列。

那么应该怎么解决呢？解决问题的关键就在于在转移的过程中不存在 $p_1,p_2$ 两个转移点使得 $[p_1,p_2]$ 被重复计算贡献。

考虑强制要求由 $[l,p]$ 构成的合法括号序列 $l,p$ 匹配。这样便可以符合要求。

$dp(l,r)\leftarrow dp(l,r)+\sum_{p=l+1}^{r-1} g(l,p) \times dp(l+1,p-1) \times dp(p+1,r)$。

举个例子来更好地了解这个过程。

拿样例 $1$ 来解释。

在计算 $dp(1,6)$ 时，只有 $p=2$ 对其产生了贡献，而 $p=4$ 时，$dp(2,3)=0$ 故并没有产生贡献。

实现

实现有一个细节，就是答案大于等于 $10^5$ 时，需要补上前导 $0$。

#include<bits/stdc++.h>

#define int long long
#define RI register int
#define ll long long

using namespace std;

namespace IO{
	inline int read(){
		RI X=0, W=0;register char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(int x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
}using namespace IO;

const int MAXN = 205;
const int mod = 1e5;

int n;
int dp[MAXN][MAXN];
int br[MAXN];

bool mark[MAXN][MAXN];

char s[MAXN];

inline int match(int x, int y){
	if(br[x]==0 && br[y]>0) return 1;
	if(br[y]==0 && br[x]<0) return 1;
	if(br[x]<0 && br[x]+br[y]==0) return 1;
	if(br[x]==br[y] && br[x]==0) return 3;
	return 0;
}

signed main(){
	n=read();scanf("%s",s+1);
	for(int i=1;i<=n+1;++i) dp[i][i-1]=1;
	for(int i=1;i<=n;++i){
		if(s[i]=='?') br[i]=0;
		if(s[i]=='(') br[i]=-1;
		if(s[i]==')') br[i]=1;
		if(s[i]=='[') br[i]=-2;
		if(s[i]==']') br[i]=2;
		if(s[i]=='{') br[i]=-3;
		if(s[i]=='}') br[i]=3;
	}
	for(int len=2;len<=n;len+=2){
		for(int i=1, j;i+len-1<=n;++i){
			j=i+len-1;
			dp[i][j]=dp[i+1][j-1]*match(i,j);
			if(dp[i+1][j-1]*match(i,j)) mark[i][j]|=mark[i+1][j-1];
			if(dp[i][j]>=mod) dp[i][j]-=mod;
			for(int p=i+1;p<j;p+=2){
				dp[i][j]+=(1ll*dp[i+1][p-1]*dp[p+1][j]*
				match(i,p));
				if(1ll*dp[i+1][p-1]*dp[p+1][j]*match(i,p)) mark[i][j]|=mark[i+1][p-1]|mark[p+1][j];
				if(dp[i][j]>=mod) mark[i][j]=1, dp[i][j]%=mod;
			} 
		}
	}
	if(mark[1][n]){
		int tot=0, ans[20];
		while(dp[1][n]) ans[++tot]=dp[1][n]%10, dp[1][n]/=10;
		for(int i=5;i>tot;--i) write(0);
		for(int i=tot;i>=1;--i) write(ans[i]);
		putchar(10);
	}
	else write(dp[1][n]);
	return 0;
}