题目链接：http://codeforces.com/problemset/problem/149/D
继续区间DP啊。。。。
思路：
定义dp[l][r][c1][c2]表示对于区间(l,r)来说,l用c1染色,r用c2染色的方案数。
那么：
1，如果括号l和括号r匹配(即括号l和r为一对括号)那么dp[l][r][c1][c2]+=dp[l+1][r-1][i][j](i与c1为不同的颜色,j与c2是不同的颜色,或i=0或j=0)
2，如果括号l和括号r不匹配,那么dp[l][r][c1][c2]+=dp[l][m(l)][c1][i]*dp[m(l)+1][r][j][c2];(i与c1为不同的颜色或i=0,j与c2不同，或j=0)(m(l))表示与l匹配的右括号的位置
代码实现，我用的是记忆化搜索的方式：
1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<stack> 5 #include<cstring> 6 using namespace std; 7 char s[710]; 8 stack<int>q; 9 int n; 10 int m[710]; 11 long long int dp[710][710][3][3]; 12 long long int ans; 13 #define MOD 1000000007 14 void init() 15 { 16 memset(m,0,sizeof(m)); 17 memset(dp,-1,sizeof(dp)); 18 ans=0; 19 } 20 void Match_Bracks() 21 { 22 while(!q.empty()) q.pop(); 23 for(int i=0;i<n;i++) 24 { 25 if(s[i]=='(') q.push(i); 26 else 27 { 28 int k=q.top(); 29 m[k]=i; 30 q.pop(); 31 } 32 } 33 } 34 bool check(int a,int b) 35 { 36 if(a==0||b==0||a!=b) return true; 37 return false; 38 } 39 int kk=0; 40 long long int dfs(int l,int r,int c1,int c2) 41 { 42 long long int sum=0; 43 44 if(dp[l][r][c1][c2]>=0) return dp[l][r][c1][c2]; 45 if(m[l]==r&&r) 46 { 47 if((c1==0&&c2)||(c2==0&&c1)) 48 { 49 if(l+1==r) 50 return dp[l][r][c1][c2]=1; 51 for(int i=0;i<3;i++) 52 for(int j=0;j<3;j++) 53 if(check(i,c1)&&check(j,c2)) 54 sum=(sum+dfs(l+1,r-1,i,j)%MOD)%MOD; 55 } 56 else return dp[l][r][c1][c2]=0; 57 } 58 else 59 { 60 for(int i=0;i<3;i++) 61 for(int j=0;j<3;j++) 62 if(check(i,j)) 63 sum=(sum+dfs(l,m[l],c1,i)*dfs(m[l]+1,r,j,c2)%MOD)%MOD; 64 } 65 return dp[l][r][c1][c2]=sum%MOD; 66 } 67 int main() 68 { 69 while(scanf("%s",s)!=EOF) 70 { 71 init(); 72 n=strlen(s); 73 Match_Bracks(); 74 for(int i=0;i<3;i++) 75 for(int j=0;j<3;j++) 76 ans=(ans+dfs(0,n-1,i,j)%MOD)%MOD; 77 cout<<ans<<endl; 78 } 79 return 0; 80 }