题解CF149D Coloring Brackets

CF149D Coloring Brackets
一道很有意思的区间DP
我们用0表示不染色,1表示红色,2表示蓝色
定义状态$f_{i,j,k,u}$表示将合法序列[i,j]染色且$i染为k,j染为u$的方案数
那么序列就可以分为三种情况
1°:()
$f_{i,j,0,1}=f_{i,f,1,0}=f_{i,j,0,2}=f_{i,j,2,0}$
2°:((…))
$f_{i,j,0,k}=\sum\limits_{u=0}^{u \le 2} \sum\limits_{v=0}^{v \le 2,v \ne k}f_{i+1,j-1,u,v}$
$f_{i,j,k,0}=\sum\limits_{u=0}^{u \le 2,u \ne k} \sum\limits_{v=0}^{v \le 2}f_{i+1,j-1,u,v}$
3°:(…)(…)
用$l,rr,ll,r$分别表示上面括号的位置
$f_{l,r,u,v}=\sum\limits_{a=0}^{a \le 2} \sum\limits_{b=0}^{b \le 2} \sum\limits_{c=0}^{c \le 2} \sum\limits_{d=0}^{d \le 2}f_{l,rr,a,b}*f_{ll,r,c,d}$并且需要满足端点颜色不同
那么只需要递归转移状态即可
代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MOD = 1000000007;

char str[705];
int stk[705], top, poi[705], col[705];
long long f[705][705][3][3];

void dfs(int l, int r)
{
    if (l + 1 == r)
        f[l][r][1][0] = f[l][r][2][0] = f[l][r][0][2] = f[l][r][0][1] = 1;
    else if (poi[l] == r)
    {
        dfs(l + 1, r - 1);
        for (int i = 0; i <= 2; i++)
            for (int j = 0; j <= 2; j++)
            {
                if (j != 2)
                    f[l][r][0][2] = (f[l + 1][r - 1][i][j] + f[l][r][0][2]) % MOD;
                if (j != 1)
                    f[l][r][0][1] = (f[l + 1][r - 1][i][j] + f[l][r][0][1]) % MOD;
                if (i != 2)
                    f[l][r][2][0] = (f[l + 1][r - 1][i][j] + f[l][r][2][0]) % MOD;
                if (i != 1)
                    f[l][r][1][0] = (f[l + 1][r - 1][i][j] + f[l][r][1][0]) % MOD;
            }
    }
    else 
    {
        dfs(l, poi[l]), dfs(poi[l] + 1, r);
        for (int i = 0; i <= 2; i++)
        {
            for (int j = 0; j <= 2; j++)
            {
                if (j > 0 && j == i)
                    continue;
                for (int k = 0; k <= 2; k++)
                    for (int u = 0; u <= 2;u++)
                        f[l][r][k][u] = (f[l][r][k][u] + f[l][poi[l]][k][i] * f[poi[l] + 1][r][j][u]) % MOD;
            }
        }
    }
}

int main()
{
    scanf("%s", str + 1);
    int len;
    for (int i = 1; str[i]; i++)
    {
        if (str[i] == '(')
            stk[++top] = i;
        else if(str[i] == ')')
            poi[stk[top--]] = i;
        len = i;
    }
    dfs(1, len);
    long long ans = 0;
    for (int i = 0; i <= 2; i++)
    {
        for (int j = 0; j <= 2; j++)
            ans = (ans + f[1][len][i][j]) % MOD;
    }
    printf("%lld", ans);
    return 0;
}