http://codeforces.com/contest/149/problem/D
题目描述：
给一个合法的括号串，然后问这串括号有多少种涂色方案，当然啦！涂色是有限制的。
1,每个括号只有三种选择：涂红色，涂蓝色，不涂色。
2,每对括号有且仅有其中一个被涂色。
3,相邻的括号不能涂相同的颜色，但是相邻的括号可以同时不涂色。
思路:dp:f[i][j][k][l]代表i到j这个区间,左边为k颜色，右边为l颜色
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #define ll long long const ll Mod=1000000007; int id[200005],n; ll f[705][705][3][3]; int c[200005]; char s[200005]; int read(){ int t=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} return t*f; } void dp(int L,int R){ if (L>R) return; if (L+1==R){ f[L][R][0][0]=0;f[L][R][0][1]=1;f[L][R][0][2]=1;f[L][R][1][0]=1;f[L][R][2][0]=1;f[L][R][1][1]=0;f[L][R][2][2]=0;f[L][R][2][1]=0;f[L][R][1][2]=0; return; } if (id[L]==R){ dp(L+1,R-1); for (int i=0;i<3;i++) for (int j=0;j<3;j++) if (((i>0)^(j>0))) for (int k=0;k<3;k++) for (int l=0;l<3;l++) if ((i==0||k==0||i!=k)&&(j==0||l==0||j!=l)) (f[L][R][i][j]+=f[L+1][R-1][k][l])%=Mod; return; } dp(L,id[L]); dp(id[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 l=0;l<3;l++) if (j==0||k==0||j!=k) (f[L][R][i][l]+=(f[L][id[L]][i][j]*f[id[L]+1][R][k][l])%Mod)%=Mod; } int main(){ scanf("%s",s+1);n=strlen(s+1); int top=0; for (int i=1;i<=n;i++){ if (s[i]=='(') c[++top]=i; else id[c[top--]]=i; } dp(1,n); ll Ans=0; for (int i=0;i<3;i++) for (int j=0;j<3;j++) Ans=(Ans+f[1][n][i][j])%Mod; printf("%I64d ",Ans); }