CF149D Coloring Brackets

题意：给出一串合法括号，按以下规则给括号染色：

1. 每个符号可以染红色、蓝色，或者不染色；

2. 相邻两个符号不能染同一种颜色，可以都不染色；

3. 一对括号有且仅有一个符号染色。

求染色方案数。

解：状态很好设啦，dp[i][j][0/1/2][0/1/2]表示区间[i, j]两边分别染什么颜色。转移不能像一般区间dp一样枚举区间长度，因为一对括号要一起考虑。用递归来转移，从小到大处理合法的状态。最小的状态是（）。如果一个区间的两端刚好是一对括号，继承括号里的内容；如果不是，它一定能分成两组合法的括号，分别求解小区间的答案，然后用乘法定理。没事多加几个取模。

代码：

#include <bits/stdc++.h>
using namespace std;
#define maxx 705
#define maxn 25
#define maxm 205
#define ll long long
#define inf 1000000009
#define mod 1000000007
ll dp[maxx][maxx][3][3]={0};
char s[maxx];
int c[maxx]={0};
int n;
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(c[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(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,c[l]);
        dfs(c[l]+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 m=0;m<3;m++){
                        if(j==k&&j!=0) continue;
                        dp[l][r][i][m]=(dp[l][r][i][m]+((dp[l][c[l]][i][j]*dp[c[l]+1][r][k][m])%mod))%mod;
                    }
                }
            }
        }
    }
}
signed main() {
//    int T;
//    scanf("%d",&T);
//    while(T--) {;
//
//    }
    scanf("%s",s+1);
    n=strlen(s+1);
    stack<int> st;
    for(int i=1;i<=n;i++){
        if(s[i]=='(') st.push(i);
        else{
            c[st.top()]=i;
            c[i]=st.top();
            st.pop();
        }
    }
    dfs(1,n);
    ll ans=0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            ans=(ans+dp[1][n][i][j])%mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}