Coloring Brackets

题目链接：https://vjudge.net/problem/CodeForces-149D

题意：给你个完全匹配的括号序列，你现在可以给这个匹配的括号序列中的括号染色，且有三个要求：1.每个括号只有三种情况,不上色,上红色,上蓝色。2.每对括号必须只能给其中的一个上色,且必须给一个上色。3.相邻的两个不能上同色，可以都不上色。求满足条件的括号序列染色的方法数。

思路：假设不染色为0,另外两种色为1,2。那对于一个匹配的括号对来说,只允许(1,0),(2,0),(0,1),(0,2)。定义dp[l][r][i][j]表示区间[l,r]的左端点状态为i,右端点状态为j时的当前区间方案数。

可以得出当l+1=r时,只有上述四种存在方案数。

除此以外还有两种情况
1.当前处理区间[l,r]两端点恰好是一个匹配括号对
2.当前处理区间[l,r]两端点不是一个匹配括号对

情况1可以先递归处理[l+1,r−1]的方案,最后合并方案数。
情况2也可分治[l,b[l]]和[b[l]+1,r]两个区间处理。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 705;
const int mod = 1000000007;
ll dp[maxn][maxn][3][3];
char a[maxn];
stack<int> zha;
int b[maxn];
int n;
void dfs(int l,int r)
{
    if(l+1==r)//只有那四种方案
    {
        dp[l][r][1][0]=dp[l][r][0][1]=1;
        dp[l][r][2][0]=dp[l][r][0][2]=1;
        return;
    }
    if(b[l]==r)
    {
        dfs(l+1,r-1);
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
        {
            if(j!=1)
                dp[l][r][0][1]=(dp[l][r][0][1]+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(j!=2)
                dp[l][r][0][2]=(dp[l][r][0][2]+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;
        }
        return;
    }
    int mid=b[l];
    dfs(l,mid);
    dfs(mid+1,r);
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        for(int k=0;k<3;k++)
        for(int h=0;h<3;h++)
    {
         if (!(k==1&&h==1) && !(k==2&&h==2) && !(i==0&&k==0))
            dp[l][r][i][j]=(dp[l][r][i][j]+dp[l][mid][i][k]*dp[mid+1][r][h][j])%mod;
    }
}
int main()
{
    scanf("%s",a);
    n=strlen(a);
    for(int i=0;i<n;i++)
    {
        if(a[i]=='(')
            zha.push(i);
        else
        {
            b[i]=zha.top();
            b[zha.top()]=i;
            zha.pop();
        }
    }
    dfs(0,n-1);
    ll ans=0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        ans=(ans+dp[0][n-1][i][j])%mod;
    cout<<ans<<endl;
}