标题

_bestow · 2021-10-23 22:08:26 · 题解

赤裸裸的区间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] 转移即可。