CF1598F RBS 题解

好困难/ll

套路的把左括号看作是 $1$，右括号看作是 $-1$。则显然 $i$ 位置的前缀是 RBS 的充要条件是：

• 不存在 $1\le j\le i$ 满足 $j$ 位置的前缀和 $<0$。
• $i$ 位置的前缀和为 $0$。

考虑直接状压 dp，设 $f_{i,j}$ 表示当前处理了 $i$ 集合内的字符串，当前的前缀最小值是 $j$，最多有多少个 RBS 前缀。转移随便处理点东西就可以做到 $O(n2^n)$ 转移。