CF149D

题目描述
Petya遇到了一个关于括号序列的问题： 给定一个字符串S，它代表着正确的括号序列，即（“(”）与 （“)”）是匹配的。例如：“(())()” 和 “()”是正确的，“)()”与“(()”则不是正确的。 在正确的括号序列中，一个左边的括号一定是匹配一个右边的括号（反之亦然）。例如，在下图中，第 3 个括号匹配第 6 个括号，第 4 个括号匹配第 5 个括号。
现在你需要对一个正确的括号序列做涂色操作，严格满足以下三个条件：

1、每个括号要么不涂色，要么涂红色，要么涂蓝色。

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

3、相邻的括号不能涂上同一种颜色（但是可以都不涂颜色）。

求：给整个括号序列涂上颜色的方案数，答案可能比较大，对 1000000007 取模。

输入格式
输入的第一行包含一个字符串 s，（2 <= |s| <= 700）代表一个正确的括号序列。

输出格式
输出方案数。（对 10^9 + 7 取模）

样例
样例1输入
(())
样例1输出
12
样例2输入
(()())
样例2输出
40
样例3输入
()
样例3输出
4
来源：CF149D
此题的主要方法是先分类讨论，要考虑左右边界是否配对
1.如果配对
则会直接继承l+1,r-1的所有方案
2如果不配对
找到左边界配对的，并把[l,r]划分成两个区间最后俩区间方案合并

#include<bits/stdc++.h>
using namespace std;
char s[705];
int pd[705];
long long int xx[705];
long long int t=1;
long long int ans=0;
long long int qc[705][705]={0};
long long int dp[705][705][3][3]={0};//dp[l][r][配色][配色] 
void dfs(long long int l,long long int r)
{
    if(qc[l][r])//边界 
    {
        return;
    }
    qc[l][r]=1;
    if(r-l==1)
    {
        dp[l][r][0][1]=1;
        dp[l][r][0][2]=1;
        dp[l][r][1][0]=1;
        dp[l][r][2][0]=1; //（）时，配色方案为一个定值 
        return;//一定走不了了 
     } 

    if(pd[l]==r)//可匹配 所一，他的方案数来自与l+1,r-1，方案数的总和 
    {
        dfs(l+1,r-1);//算出前面的接果,不断向一个点缩 
        for(int i=0;i<=2;i++)//枚举着色 （（）） 
        {
            for(int j=0;j<=2;j++)//右边界 
            {
                for(int k=0;k<=2;k++) //左+1 
                {
                    for(int a=0;a<=2;a++)//右+1 
                    {
                        if((i==0||j==0)&&(i!=0||j!=0)&&(i!=k||(i+k==0))&&(j!=a||(j+a==0)))//1、每个括号要么不涂色，要么涂红色，要么涂蓝色。且只能将其中一个涂色。3,4、邻的括号不能涂上同一种颜色（但是可以都不涂颜色）。
                        {
                            dp[l][r][i][j]+=dp[l+1][r-1][k][a];//累加 
                            dp[l][r][i][j]%=1000000007;//因为如果l+1,r+1无发配对，会进入下一个else中，所以不用判断l+1,r-1是否配对 
                         } 
                    }
                }
            }
        }
    }
    else
    {
        dfs(l,pd[l]);
        dfs(pd[l]+1,r);//不能把pd[l]算二次，所以要+1 
        for(int i=0;i<=2;i++)//枚举着色 
        {
            for(int j=0;j<=2;j++)//与上面一样，i，j在一个括号中，i,a是左右端点 
            {
                for(int k=0;k<=2;k++)
                {
                    for(int a=0;a<=2;a++)
                    {
                        if((i==0||j==0)&&(i!=0||j!=0)&&(j!=k||(j+k==0)))// j与k是相邻的，要判断； 
                        {
                            dp[l][r][i][a]+=dp[l][pd[l]][i][j]*dp[pd[l]+1][r][k][a];//为什么要*呢？设为a   A,a可一与A,B,C和并，b也是,所以和并时，为两边之积 
                            dp[l][r][i][a]%=1000000007;//而且dp[l][r][i][a]要累加所有合并之积    b   B
                        }//                                                                                                          c   C
                    }
                }
            }
        }

    }
}
int main()
{
    scanf("%s",s+1);
    long long int n=strlen(s+1);//如果字符串+1，strlen()中的字符串也要 
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='(')
        {
            xx[t++]=i;
        }
        else
        {
            pd[xx[--t]]=i;//模拟一个栈 
        }
     } 
     /*for(int i=1;i<=n;i++)
    {
        printf("%d ",pd[i]);
    }*/
     dfs(1,n);
     for(int i=0;i<=2;i++)
     {
        for(int j=0;j<=2;j++)
        {
            ans+=dp[1][n][i][j];//加上不同配色的所有方案 
            ans%=1000000007;
         }
     }
     printf("%lld",ans);
 }