标题

赤裸裸的区间dp。设 $f[l,r]$ 区间 $[l,r]$ 可以形成多少合法串。根据题目条件得知合法串两边都必须是括号，且左边一定是左括号，右边一定是右括号。 第一种 $(S)$ 的情况，直接扫一遍 $O(n)$。然后考虑 $(A),(SA),(AS)$。第一种从 $[l+1,r-1]$ 转移，剩下的扫一遍，从 $f[i+1,r-1],f[l+1,i-1]$ ，其中 $s[l+1,i],s[i,r-1]$ 是 $S$， 转移，复杂度 $O(n)$。 最后一种考虑枚举断点，转移方程大概是 $f[l,i]\times f[j,r]$，$s[i+1,j-1]$ 是 $S$。随便前后缀和优化一些也可以做到 $O(n)$。 但是这样会算重，考虑 $(**)()*()$，会在每个断点处算一次，那么根据套路，直接让他在第一个断点被计算。 考虑给 dp 加一维状态，$f[i,j,0/1]$ 分别代表能或不能使用最后一种转移，那么 $f[l,i,0]\times f[j,r,1]$ 转移即可。