题目大意：给出一组括号，询问你给括号上色的情况数，颜色有两种，要求有两点：
①一对匹配的括号，最多且必须有一个上色，即每一对对应的括号都是一个有颜色，另一个没有颜色。
②相邻的两个字符，不能为同一种颜色，但是可以是都不染色。
dp[i][j][k1][k2]表示区间[i,j]且i为颜色k1、j为颜色k2时，合法解的数目。我们可以假设0为不染色、1和2为另外两种颜色。
DP方程有两个部分，第一部分为当i和j为一对匹配的括号时，需要注意满足条件一。
第二部分为当i匹配的后半括号时，注意条件二来进行状态转移。
这里分别拿出一个例子来详细说明：
b[i]为处理出来的辅助数组，值的意义为a[i]字符对应另一半括号的位置。左右括号相互标明。
①dp[i][j][0][1]+=(dp[i+1][j-1][0][0]+dp[i+1][j-1][0][2]+dp[i+1][j-1][1][0]+dp[i+1][j-1][1][2]+dp[i+1][j-1][2][0]+dp[i+1][j-1][2][2])%mod;
因为左边没染色，右边为颜色1，所以左边i+1无颜色限制而右边的j-1不能为颜色1，能够转移到这个状态的状态有6个。枚举k1，k2的值，并且注意写全能够继承的状态。
② if(k3==0||k4==0||k3!=k4)
{
dp[i][j][k1][k2]+=(dp[i][b[i]][k1][k3]*dp[b[i]+1][j][k4][k2])%mod;
dp[i][j][k1][k2]%=mod;
}
枚举k1，k2，k3，k4.此时的 i和 j 一定不匹配，所以可以存在所有的3X3=9种的组合，需要注意的只有相互匹配的k1与k3（受限于条件1）与k3和k4（受限于条件2）。 此情况只有讨论到合法解时值才不为0，如若遇到dp[i][j][0][0]这种，那么会由于值为0而使结果不改变，不影响答案。
具体代码如下：
#include<iostream> using namespace std; #define ll long long const ll mod=1000000007; ll dp[705][705][3][3]; int b[705],c[360]; int main() { string a; cin>>a; int n=a.size(); int i,k,j,s=1; for(i=0;i<n;i++) { if(a[i]=='(') c[s++]=i; else { b[c[s-1]]=i; b[i]=c[s-1]; s--; } } for(i=0;i<n-1;i++) if(b[i]==i+1) { dp[i][i+1][0][1]=dp[i][i+1][1][0]=1; dp[i][i+1][0][2]=dp[i][i+1][2][0]=1; //dp[i][i+1][0][0]=1; } for(k=1;k<n;k++) for(i=0;i+k<n;i++) { j=i+k; if(b[i]==j) { dp[i][j][0][1]+=(dp[i+1][j-1][0][0]+dp[i+1][j-1][0][2]+dp[i+1][j-1][1][0]+dp[i+1][j-1][1][2]+dp[i+1][j-1][2][0]+dp[i+1][j-1][2][2])%mod; dp[i][j][0][2]+=(dp[i+1][j-1][0][0]+dp[i+1][j-1][0][1]+dp[i+1][j-1][1][0]+dp[i+1][j-1][1][1]+dp[i+1][j-1][2][0]+dp[i+1][j-1][2][1])%mod; dp[i][j][1][0]+=(dp[i+1][j-1][0][0]+dp[i+1][j-1][0][1]+dp[i+1][j-1][0][2]+dp[i+1][j-1][2][0]+dp[i+1][j-1][2][1]+dp[i+1][j-1][2][2])%mod; dp[i][j][2][0]+=(dp[i+1][j-1][0][0]+dp[i+1][j-1][0][1]+dp[i+1][j-1][0][2]+dp[i+1][j-1][1][0]+dp[i+1][j-1][1][1]+dp[i+1][j-1][1][2])%mod; } else if(b[i]<j) { int k1,k2,k3,k4; for(k1=0;k1<=2;k1++) for(k2=0;k2<=2;k2++) for(k3=0;k3<=2;k3++) for(k4=0;k4<=2;k4++) { if(k3==0||k4==0||k3!=k4) { dp[i][j][k1][k2]+=(dp[i][b[i]][k1][k3]*dp[b[i]+1][j][k4][k2])%mod; dp[i][j][k1][k2]%=mod; } } } } ll ans=0; for(i=0;i<=2;i++) for(j=0;j<=2;j++) { //cout<<dp[0][n-1][i][j]<<endl; ans=(ans+dp[0][n-1][i][j])%mod; } cout<<ans<<endl; }