【CodeForces-149D】Coloring Brackets

题意#

给定一个合法括号序列，对序列按照如下方法染色：

1. 每个括号的颜色：红色、蓝色、或不染色；
2. 每对匹配的括号：有且仅有其中一个被染色；
3. 相邻两个括号：若都有颜色，要求它们的颜色互不相同。

求符合条件的染色方案数，对 $10^9+7$ 取模。

序列长度：$2\leq |s|\leq 700$.

分析#

区间DP.

将颜色映射到三个数：

设 $f[l][r][x][y]$ 为区间 $[l, r]$ 内，且 $\operatorname{Color}_l=x, \operatorname{Color}_r=y$ 的方案数。

下面分类讨论状态转移方式：#

情况一：$()$#

若 $l+1=r$，则这段序列仅有一对左右括号，只能对其中一个染色。

作为初始情况，可直接赋值：

情况二：$(\dots\dots)$#

若 $l$ 与 $r$ 配成一对括号，则枚举 $\operatorname{Color}_{l+1}$ 和 $\operatorname{Color}_{r-1}$，从 $f[l+1][r-1]$ 进行转移。

情况三：$(\dots\dots) \dots(\dots)$#

要求 $l$ 是左括号，$r$ 是右括号。设 $\operatorname{R}[i]$ 表示与 $i$ 配对的右括号。

用 $f[l][\operatorname{R}[l]]\times f[\operatorname{R[l]+1}][r]$ 进行转移，具体过程要枚举四个颜色，就不做形式化表达了。

for(int i = 0; i <= 2; i++) {
    for(int j = 0; j <= 2; j++) {
        for(int p = 0; p <= 2; p++) {
            for(int q = 0; q <= 2; q++) {
                if((j == 1 && p == 1) || (j == 2 && p == 2)) continue;
                (f[l][r][i][q] += (f[l][R[l]][i][j] * f[R[l] + 1][r][p][q]) % mod) %= mod;
            }
        }
    }
}