Description

题目链接

给定一个配对的括号序列，求染色方案。染色规则如下：

1. 一个括号可以染红色、蓝色或不染色
2. 一对匹配的括号需要且只能将其中一个染色
3. 相邻两个括号颜色不能相同（但可以都不染色）

Solution

一道区间 dp 的好题。

括号配对

这个，不用多说了吧。

令 right[i] 为第 $i$ 个括号的配对括号。

代码很好写：

scanf("%s",s+1);
int n=strlen(s+1);
for(int i=1;i<=n;i++){
    if(s[i]=='(')stk.push(i);
    else{
        right[stk.top()]=i;
        right[i]=stk.top();
        stk.pop();
    }
}

具体原理很简答，可以看 UVA673 平衡的括号 Parentheses Balance。

设计状态

看到题后第一反应当然是令 dp[l][r] 为将区间 $[l,r]$ 内染色的总方案数。

但是题目上说：

1. 一个括号可以染红色、蓝色或不染色
2. 一对匹配的括号需要且只能将其中一个染色
3. 相邻两个括号颜色不能相同（但可以都不染色）

有了这些限制之后，我们发现，如果单纯地定义 dp[l][r] 为将区间 $[l,r]$ 内染色的总方案数，很难转移。

换句话说，我们还需要更多的信息来进行转移。

其实只需要增加这个区间两端的括号颜色，就可以进行转移了。

那么就设计 dp[l][r][p][q] 为将区间 $[l,r]$ 内染色的总方案数，且最左边的括号颜色为 $p$，最右边的括号颜色为 $q$。

其中 $p,q$ 的值为 $0$ 时代表不染色，为 $1$ 时代表蓝色，为 $2$ 时代表红色。

转移方程

首先是初始条件：如果 $r=l+1$，那么 $[l,r]$ 一定是一对匹配的括号。

所以有 dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;。

毕竟整个区间长度就是 $2$，那么一旦左、右端点的颜色确定了，整个区间的染色方案自然也就确定了，所以只有一种。

由于「一对匹配的括号需要且只能将其中一个染色」，所以 dp[l][r][0][0]=dp[l][r][1][2]=dp[l][r][2][1]=dp[l][r][1][1]=dp[l][r][2][2]=0，不必再专门这五种专门赋值了。

然后，转移的时候，需要分类讨论：

• 如果第 $l$ 个括号刚好和第 $r$ 个括号配对：

那么这个区间类似于这样：(......)。

所以易知 dp[l][r][0][0]=dp[l][r][1][2]=dp[l][r][2][1]=dp[l][r][1][1]=dp[l][r][2][2]=0。原因和上面一样。

所以这五个就不需要再转移了。

至于剩下的四种情况，以 dp[l][r][0][1] 为例：

由于左端点不染色，右端点是 $1$
所以它不能 dp[l+1][r-1][·][1] 转移过来。
否则相邻两个括号的颜色相同，就不符合条件了。

那么我们从 $0$ 到 $2$ 枚举 $i,j$，然后看 $i,j$ 的值来一个一个转移即可。

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

• 如果第 $l$ 个括号刚好和第 $r$ 个括号不配对：

那么我们找出与第 $l$ 个括号配对的括号。

区间大概是这样的：(......)...(

那么我们分别处理出区间 $[l,\texttt{right[l]}]$ 的方案数和区间 $[\texttt{right[l]}+1,r]$ 的方案数，然后相乘即可。

需要注意的是，$\texttt{right[l]}$ 与 $\texttt{right[l]}+1$ 处的括号颜色不能相同。这种情况需要特判。

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;//right[l] 与 right[l]+1 处的括号颜色相同
                dp[l][r][i][q]+=(dp[l][right[l]][i][j]*dp[right[l]+1][r][p][q]%mod);
                dp[l][r][i][q]%=mod;
            }
        }
    }
}

那么，转移方式就弄好啦！

有一个需要注意的点就是：转移顺序最好是以记忆化搜索的顺序来，不然的话会很麻烦。

最后，上代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<stack>

#define MAXN 800
#define int long long

using namespace std;

char s[MAXN];
int dp[MAXN][MAXN][5][5],right[MAXN];
stack<int>stk;

const int mod=1000000007;

void DFS(int l,int r){
    if(r==l+1){
        dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;
    }
    else if(right[l]==r){//l,r 配对
        DFS(l+1,r-1);//先处理出来 [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+1][r-1][i][j],dp[l][r][0][1]%=mod;
                if(j!=2)dp[l][r][0][2]+=dp[l+1][r-1][i][j],dp[l][r][0][2]%=mod;
                if(i!=1)dp[l][r][1][0]+=dp[l+1][r-1][i][j],dp[l][r][1][0]%=mod;
                if(i!=2)dp[l][r][2][0]+=dp[l+1][r-1][i][j],dp[l][r][2][0]%=mod;
            }
        }
        //刚才说过的转移方程
    }
    else{
        DFS(l,right[l]);
        DFS(right[l]+1,r);
        //先处理区间 [l,right[l]] 和区间 [right[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][right[l]][i][j]*dp[right[l]+1][r][p][q]%mod);
                        dp[l][r][i][q]%=mod;
                    }
                }
            }
        }
    }
}

signed main(void){

    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;i++){
        if(s[i]=='(')stk.push(i);
        else{
            right[stk.top()]=i;
            right[i]=stk.top();
            stk.pop();
        }
    }
    //处理出配对的括号

    DFS(1,n);

    int ans=0;
    for(int i=0;i<=2;i++){
        for(int j=0;j<=2;j++){
            ans+=dp[1][n][i][j];
            ans%=mod;
        }
    }

    printf("%lld\n",ans);

    return 0;
}