题意：原题在这
给出一个配对的括号序列（如"(())()"、"()"等， ")()"、"(()"是不符合要求的 ），对该序列按以下方法进行染色： 1.一个括号可以染红色、蓝色或不染色 2.一对匹配的括号需要且只能将其中一个染色 3.相邻两个括号颜色不能相同（但可以都不染色） 求符合条件的染色方案数（对1000000007取模） 输入：
一行，表示括号序列 输出：
一个数表示方案数（对1000000007取模） 数据范围：
2<=序列长度<=700
做法：（详见行内注释）
1. 情况：
（1）首尾直接连接
（2）某个括号的结尾刚好为串尾
（3）相邻不同色
2. dp[l][r][0/1/2][0/1/2]表示括号区间[l，r]左/右染色情况下的最大方法数
3. 预处理，dfs，输出dp范围一定是[0,n);
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define maxn 99999999 #define mod 1000000007 using namespace std; string s; int n,cnt=-1; int head[950],tail[950]; long long ans=0; long long dp[950][950][5][5]; void dfs(int l,int r) { //if(l>r) return 1; 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; return; } else if(tail[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+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; } return; } else {//第二种情况 dfs(l,tail[l]); dfs(tail[l]+1,r); for(int i=0;i<=2;i++) for(int j=0;j<=2;j++) for(int f=0;f<=2;f++) for(int k=0;k<=2;k++) {//颜色不能一样 if(j==1&&f==1) continue; if(j==2&&f==2) continue; dp[l][r][i][k]=(dp[l][r][i][k]+(dp[l][tail[l]][i][j]*dp[tail[l]+1][r][f][k])%mod)%mod; } return; } } int main() { cin>>s; n=s.size(); for(int i=0;i<n;i++)//预处理每一个括号的另一半 { if (s[i]=='(') head[cnt++]=i; else tail[head[--cnt]]=i; } dfs(0,n-1); for(int i=0;i<=2;i++) for(int j=0;j<=2;j++) { ans+=dp[0][n-1][i][j]; } ans%=mod; cout<<ans<<endl; return 0; }