D

给定一个合法的括号序列
配对的括号其中一个要被染成红色或蓝色,另一个不染色
相邻的括号若都被染色,则不能为同色

区间dp

$d_{l,r,i,j}$ 表示区间 [L,R]的括号序列
区间左边括号颜色为i,右边为j

有两种转移

$d_{L,R,i,j} = \sum d_{L+1,R-1,i’,j’} \;\; if \; match(L,R)$
$d_{L,R,i,j} = \sum d_{L+1,match[L]-1,i’,j’}d_{match[L]+1,R,j’,j} \;\; if \; not \; match(L,R)$

注意i' j' 需要满足题目条件