P7914

题目链接 CSP 考前做下历年真题。 转移很多，我刚开始设 $dp1[i][j]$ 为 $i$ 到 $j$ 合法的方案数，$dp2[i][j]$ 为左边一段 $*$，右边是合法的方案数，以及 $dp3[i][j]$，右边是 $*$，左边合法。 然后就进坑了，比如 $()()()$，会在第二个位置统计 ......

和`CF149D Coloring Brackets`（B题）一样，都是关于括号的区间DP。 在B题中，有一个细节，就是在枚举断点时枚举到第一个就要`break`，这是为了使每种方案只贡献一次，防止一种方案中有多个符合条件的断点。 此题中，因为序列的字符是不变的，所以直接`break`就行了。 但是 ......

主要参考：[洛谷题解](https://www.luogu.com.cn/blog/wsyear/solution-p7914 ) # [CSP-S 2021] 括号序列 ## 题目描述 小 w 在赛场上遇到了这样一个题：一个长度为 $n$ 且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确 ......