CF149D Coloring Brackets 题解

题意：给出一个配对的括号序列（如 “$\texttt{(())()}$”、“$\texttt{()}$” 等，“$\texttt{)()}$”、“$\texttt{(()}$”是不符合要求的），对该序列按照以下方法染色。

一个括号可以染成红色、蓝色或者不染色。

一对匹配的括号需要且只能将其中一个染色。

相邻两个括号颜色不能相同（但都可以不染色）。

求符合条件的染色方案数，对 $1000000007$ 取模。

容易发现这个题目就是个区间dp

但是仅仅用 $dp[l][r]$ 并不能表示出两侧括号的颜色

因此设 $dp[l][r][i][j]$ 为区间 $[l,r]$ 内且左右两侧的颜色分别为 $i,j$ 时的方案数（0为不染色，1为红，2为蓝）

考虑边界：当 $l+1=r$ 时，有

$\text{()}$

dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;

一般地，

当 $l$ 与 $r$ 配对时，有

$\text{(}\dots\text{)}$

for(int i=0; i<=2; i++)
    for(int j=0; j<=2; j++)
    {
        if(j!=1) dp[l][r][0][1]=(dp[l][r][0][1]+dp[l+1][r-1][i][j])%mod;
        if(j!=2) dp[l][r][0][2]=(dp[l][r][0][2]+dp[l+1][r-1][i][j])%mod;
        if(i!=1) dp[l][r][1][0]=(dp[l][r][1][0]+dp[l+1][r-1][i][j])%mod;
        if(i!=2) dp[l][r][2][0]=(dp[l][r][2][0]+dp[l+1][r-1][i][j])%mod;
    }

当 $l$ 与 $r$ 不配对时，有

$\text{(}\dots\text{)}\dots\text{(}\dots\text{)}$

以及

$\text{(}\dots\text{)}\text{(}\dots\text{)}$

等情况，不过本质上是一样的

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;
                dp[l][r][i][q]=(dp[l][r][i][q]+dp[l][mch[l]][i][j]*dp[mch[l]+1][r][p][q]%mod)%mod;
            }

值得注意的是，本题并不适用一般的dp顺序，而是采用记忆化搜索

因为本题要求配对的括号有且仅有一个被染色，而一般的顺序难以保证配对的括号在同一个区间内，即不能保证转移中用到的序列都是合法的，因此较为麻烦

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(705)
const int mod=1e9+7;
char a[N];
int n,mch[N],stk[N],top,dp[N][N][3][3];
void dfs(int l,int r)
{
    if(l+1==r)dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;
    else if(mch[l]==r)
    {
        dfs(l+1,r-1);
        for(int i=0; i<=2; i++)
            for(int j=0; j<=2; j++)
            {
                if(j!=1) dp[l][r][0][1]=(dp[l][r][0][1]+dp[l+1][r-1][i][j])%mod;
		        if(j!=2) dp[l][r][0][2]=(dp[l][r][0][2]+dp[l+1][r-1][i][j])%mod;
		        if(i!=1) dp[l][r][1][0]=(dp[l][r][1][0]+dp[l+1][r-1][i][j])%mod;
		        if(i!=2) dp[l][r][2][0]=(dp[l][r][2][0]+dp[l+1][r-1][i][j])%mod;
            }
    }else
    {
        dfs(l,mch[l]);dfs(mch[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;
                        dp[l][r][i][q]=(dp[l][r][i][q]+dp[l][mch[l]][i][j]*dp[mch[l]+1][r][p][q]%mod)%mod;
                    }
                        
    }
}
signed main()
{
    scanf("%s",(a+1));
    n=strlen(a+1);
    for(int i=1; i<=n; i++)
    {
        if(a[i]=='(')stk[++top]=i;
        else mch[stk[top]]=i,mch[i]=stk[top],--top;
    }
    dfs(1,n);
    int ans=0;
    for(int i=0; i<=2; i++)
        for(int j=0; j<=2; j++)
            ans=(ans+dp[1][n][i][j])%mod;
    printf("%lld\n",ans);
    return 0;
}