D - Coloring Brackets
CodeForces - 149D
题目描述：
给一个合法的括号串，然后问这串括号有多少种涂色方案，当然啦！涂色是有限制的。
1,每个括号只有三种选择：涂红色，涂蓝色，不涂色。
2,每对括号有且仅有其中一个被涂色。
3,相邻的括号不能涂相同的颜色，但是相邻的括号可以同时不涂色。
问有多少种染色方式
思路：
先说一个点：(())这样的括号序列在涂色的时候，第一个括号与第三个括号是不可以看做是一对。最后发现并不是这样的，给出的括号序列，括号的匹配都是固定的，也就是说只需要给这些固定匹配的括号按照上面限制涂色就好，所以一个栈就能求出mapp[i], mapp[i]=j表示下标i和j匹配。
可以定义 dp[l][r][x][y] 表示区间 [l, r] 在左端点涂x色，右端点涂y色的情况下的方案数。其中0代表不涂色， 1代表涂红色， 2代表涂蓝色。
窝们可以把括号序列可以分为两类分别进行状态转移：
括号套括号，状态转移是：dp[l][r][x][y] += dp[l+1][r-1][x'][y'] (0<=x'<3, x'!=x, 0<=y'<3, y!=y')
多个匹配串连起来，转台转移是：dp[l][r][x][y] += dp[l][nu][x'][y'] * dp[nu][r][x''][y''] (nu是l对应的另一边括号)
边界条件：
当l+1 == r的时候有：dp[l][r][0][1] = 1; dp[l][r][1][0] = 1;
dp[l][r][0][2] = 1; dp[l][r][2][0] = 1;
代码：
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
char s[710];
int n,mapp[710]; //mapp[i]=j表示下标i和j匹配
long long dp[710][710][3][3];
void getmap() ///找出配对情况
{memset(mapp,0,sizeof(mapp));stack<int>q;while(!q.empty()) q.pop();for(int i=0; i<n; i++){if(s[i]=='(') q.push(i);else{if(q.empty()) continue;int p=q.top();q.pop();mapp[p]=i;mapp[i]=p;}}
}
void DPfunc()
{n=strlen(s);getmap();memset(dp,0,sizeof(dp));for(int i=0; i<n-1; i++) ///对相邻的初始化{dp[i][i+1][0][1]=dp[i][i+1][0][2]=dp[i][i+1][1][0]=dp[i][i+1][2][0]=1;}for(int len=2; len<=n; len++) {for(int i=0; i<n; i++) ///开始位置{int j=i+len-1;if(j>=n) continue;if(mapp[i]==j) ///i和j位置的括号是匹配的{for(int p=0; p<=2; p++){for(int q=0; q<=2; q++){if(q!=1)dp[i][j][0][1]=(dp[i][j][0][1]+dp[i+1][j-1][p][q])%mod;if(p!=1)dp[i][j][1][0]=(dp[i][j][1][0]+dp[i+1][j-1][p][q])%mod;if(q!=2)dp[i][j][0][2]=(dp[i][j][0][2]+dp[i+1][j-1][p][q])%mod;if(p!=2)dp[i][j][2][0]=(dp[i][j][2][0]+dp[i+1][j-1][p][q])%mod;}}}else ///i和j位置的括号是不匹配的{int u=mapp[i]; for(int p=0; p<=2; p++)for(int q=0; q<=2; q++)for(int x=0; x<=2; x++)for(int y=0; y<=2; y++)if(!((x==1&&y==1)||(x==2&&y==2))) //保证u和U+1不是同一种颜色dp[i][j][p][q]=(dp[i][j][p][q]+(dp[i][u][p][x]*dp[u+1][j][y][q])%mod)%mod;}}}
}
int main()
{while(~scanf("%s",s)){DPfunc();long long ans=0;for(int i=0; i<=2; i++)for(int j=0; j<=2; j++)ans=(ans+dp[0][n-1][i][j])%mod;printf("%lld\n",ans);}return 0;
}