Coloring Brackets
题目链接：
http://www.codeforces.com/contest/149/problem/D
题意：
给出一个只"("和")"的序列，序列合法（即所有的括号一一配对），现要给这个序列染色，规则如下:
①每个括号都只能染成红色或者蓝色，或者不染色
②每对括号必须有且只能有一个括号染色
③相邻的括号不能染成同一个颜色，但可以同时不染色
求染色的方案数
题解：
设dp[i][j][x][y]为将区间[i,j]的左端点 i 染成 x ，将右端点 j 染成y的方案数，这道题直接用for循环跑区间DP可能会比较麻烦，用记忆化搜索会简单很多，由于序列是合法的，那么与每个括号相匹配的位置都是固定的，因此只需要考虑()()和(())两种情况便可。
对于情况"()()"，要将其不同部分的方案数相乘（详见代码）
对于情况"(())"，只需要找出所有满足dp[i][j][x][y]对应要求的dp[i+1][j-1][xx][yy]即可
代码
#include<stdio.h>
#include<string.h>
#define MOD 1000000007
const int N=701;
long long dp[N][N][3][3];
char s[N];
int to[N];
long long mmax(long long x,long long y)
{
return x>y?x:y;
}
void Get_Dp(int start,int t)
{
if(start>t)return;
int ans1[3][3]={0},ans2[3][3]={0};
for(int j=t;j>=start;--j)
if(s[j]==')')
{
int i=to[j];
if(i+1==j)
{
for(int xx=0;xx<3;++xx)
for(int yy=0;yy<3;++yy)
if(xx!=yy&&(!xx||!yy)&&(xx||yy))
{
dp[i][j][xx][yy]=1;
}
}
else Get_Dp(i+1,j-1);
for(int x=0;x<3;++x)
for(int y=0;y<3;++y)
if((x||y)&&(!x||!y))
{
for(int xx=0;xx<3;++xx)
for(int yy=0;yy<3;++yy)
if(((xx!=x||!x)&&(yy!=y||!y)))
{
dp[i][j][x][y]=(dp[i][j][x][y]+dp[i+1][j-1][xx][yy])%MOD;
}
if(j==t)ans2[x][y]=dp[i][j][x][y],ans1[x][y]=0;//这一部分是对()()情况的处理
else
{
for(int xx=0;xx<3;++xx)
for(int yy=0;yy<3;++yy)
if((y!=xx||!xx))
{
ans1[x][yy]=(ans1[x][yy]+dp[i][j][x][y]*ans2[xx][yy])%MOD;
}
}
}
if(j!=t)
{
for(int x=0;x<3;++x)
for(int y=0;y<3;++y)
ans2[x][y]=ans1[x][y],ans1[x][y]=0;
}
j=i;
}
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)
dp[start][t][i][j]=ans2[i][j];
}
void solve()
{
long long res=0;
memset(dp,0,sizeof(dp));
memset(to,0,sizeof(to));
scanf("%s",s+1);
s[0]='?';
int t=strlen(s)-1;
for(int i=1;i<=t;++i)
if(s[i]==')')
{
for(int j=i-1;j>=1;--j)
if(s[j]=='('&&!to[j])
{
to[i]=j;
to[j]=i;
break;
}
}
Get_Dp(1,t);
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)
{
res=(res+dp[1][t][i][j])%MOD;
}
printf("%lld
",res);
}
int main()
{
solve();
return 0;
}