CF149D Coloring Brackets
题面：
给出一个配对的括号序列（如"((())())"、"(())"等， "()())"、"((())"是不符合要求的 ），对该序列按以下方法进行染色：
- 1.一个括号可以染红色、蓝色或不染色
- 2.一对匹配的括号需要且只能将其中一个染色
- 3.相邻两个括号颜色不能相同（但可以都不染色） 求符合条件的染色方案数（对1000000007取模）
输入：一行，表示括号序列
输出：一个数表示方案数（对1000000007取模） 数据范围：
这道题转移很恶心，并且也比较难想。是一道很仙的区间 (dp) 题。
想了半天，发现只会打爆搜，最后看了看题解 才把这题搞懂
按照区间dp的套路我们还是设 (f[l][r]) 表示从 (l) 刷到 (r) 的合法方案数。
这是，我们还要填上一维颜色，因为限制是和颜色相关的。
(f[l][r][0,1,2][0,1,2]) 表示从(l) 刷到 (r) 且 (l) 不涂/涂红色/涂蓝色， (r) 不涂/涂红色/涂蓝色的方案数。
边界 (l +1 == r)：
-
(l) 和 (r) 不配对，就是这种情况 ("((") ，就要保证 (l) 和 (r) 的颜色不同就行，还要算上他们两个都不涂的情况。
-
if(match[l] != r) f[l][r][0][0] = f[l][r][0][1] = f[l][r][0][2] = f[l][r][1][0] = f[l][r][2][0] = 1 -
(l) 和 (r) 配对的情况，就不能算 两个都不涂的情况
-
if(match[l] == r) f[l][r][0][1] = f[l][r][0][2] = f[l][r][1][0] = f[l][r][2][0] = 1
转移的时候：
(l) 和 (r) 匹配的时候，也就是 ("(....)") 的情况
我们就只需要考虑 (l) 和 (l+1) 以及 (r-1) 和 (r) 颜色不相同的情况，大力枚举 (l+1) 和 (r) 的颜色就行。
至于为什么不枚举 (l) 和 (r) 的颜色，因为那样写太复杂了，你完全可以只考虑 (l) 和 (r) 的颜色符合限制的方案数。
至于其他 (l) 和 (r) 的颜色情况都不符合条件，可以直接赋为 (0)
Code
for(int i = 0; i <= 2; i++)//l+1的颜色
{
for(int j = 0; j <= 2; j++)//r-1的颜色
{//注意相邻的颜色不能相同，也就是不能发生转移
if(j != 1) f[l][r][0][1] = (f[l][r][0][1] + f[l+1][r-1][i][j]) % p;
if(j != 2) f[l][r][0][2] = (f[l][r][0][2] + f[l+1][r-1][i][j]) % p;
if(i != 1) f[l][r][1][0] = (f[l][r][1][0] + f[l+1][r-1][i][j]) % p;
if(i != 2) f[l][r][2][0] = (f[l][r][2][0] + f[l+1][r-1][i][j]) % p;
}
}
(l) 和 (r) 不匹配的时候，也就是("()()") 的情况
这个我们把它分为两个小区间 (l -> match[l]) 以及 ({match[l]+1} -> r)
就可以递归求解了，至于为什么要分成这两个小区间。
因为你分成别的区间的话，要考虑的情况比较多，你要考虑 与 (l) 相邻的情况以及和他 匹配的那个括号的情况。
这样就可以少讨论与 (l) 相邻的情况，只需要考虑 (match[l]) 与 (match[l]+1) 相邻的情况。
然后大力枚举一下这四个点的颜色就可以了，只不过写起来有点费劲
Code
for(int i = 0; i <= 2; i++)//l的颜色
{
for(int j = 0; j <= 2; j++)//r的颜色
{
for(int k = 0; k <= 2; k++)//match[l] 的颜色
{
for(int u = 0; u <= 2; u++)//match[l+1] 的颜色
{
if(k == u && k != 0 && u != 0) continue;//相邻的颜色不能相同，但可以都不染色
f[l][r][i][j] = (f[l][r][i][j] + f[l][match[l]][i][k] * f[match[l]+1][r][j][u] % p) % p;
}
}
}
}
至于这个循环考虑了 (l) 和 (match[l]) 都不涂的情况，但那种情况的方案数为 (0) ,在乘另一个数对答案没有贡献。
最后的答案就是 (displaystyle sum_{i=0}^2 sum_{j=0}^{2} f[1][n][i][j])。 枚举一下起点和终点的颜色就可以了。
Code(我写的是记忆化搜索的放法)
当然了，你也可以写平常的那种写法。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int p = 1e9+7;
char s[710];
int n,top,ans;
int sta[710],match[710],f[710][710][3][3];
void slove(int l,int r)
{
if(l+1 == r)
{
if(match[l] != r) f[l][r][0][0] = 1;
f[l][r][0][1] = f[l][r][0][2] = f[l][r][1][0] = f[l][r][2][0] = 1;
return;
}
if(match[l] == r)//()
{
slove(l+1,r-1);
for(int i = 0; i <= 2; i++)//l+1的颜色
{
for(int j = 0; j <= 2; j++)//r-1的颜色
{
if(j != 1) f[l][r][0][1] = (f[l][r][0][1] + f[l+1][r-1][i][j]) % p;
if(j != 2) f[l][r][0][2] = (f[l][r][0][2] + f[l+1][r-1][i][j]) % p;
if(i != 1) f[l][r][1][0] = (f[l][r][1][0] + f[l+1][r-1][i][j]) % p;
if(i != 2) f[l][r][2][0] = (f[l][r][2][0] + f[l+1][r-1][i][j]) % p;
}
}
}
else//()....()
{
slove(l,match[l]); slove(match[l]+1,r);
for(int i = 0; i <= 2; i++)//l的颜色
{
for(int j = 0; j <= 2; j++)//r的颜色
{
for(int k = 0; k <= 2; k++)//match[l] 的颜色
{
for(int u = 0; u <= 2; u++)//match[l+1] 的颜色
{
if(k == u && k != 0 && u != 0) continue;//相邻的颜色不能相同，但可以都不染色
f[l][r][i][j] = (f[l][r][i][j] + f[l][match[l]][i][k] * f[match[l]+1][r][j][u] % p) % p;
}
}
}
}
}
}
signed main()
{
scanf("%s",s+1);
n = strlen(s+1);
for(int i = 1; i <= n; i++)
{
if(s[i] == '(')
{
sta[++top] = i;
}
else if(s[i] == ')')
{
int t = sta[top--];
match[t] = i;
match[i] = t;
}
}
slove(1,n);
for(int i = 0; i <= 2; i++)
{
for(int j = 0; j <= 2; j++)
{
ans = (ans + f[1][n][i][j]) % p;;
}
}
printf("%lld
",ans);
return 0;
}