url: https://www.luogu.com.cn/problem/CF149D
tag:
搜索，记忆化搜索，区间DP
思路：
使用 f[l][r][i][j] 表示区间l和r之间l为i色，r为j色时的染色方案数。有两种情况，当 l 和 r 配对时，可以由 l + 1 到 r - 1更新过来。如果不配对，由 l 到 第一个配对的括号这段区间和由那个括号后面的括号到 r 这段区间的方案数相乘。注意如果相邻的括号都有染色且颜色一样需要跳过。初始化是当 l + 1 == r 时，此时区间只有两个括号，对应的四个情况都只有一种方案。最后dfs之后将所有可能的答案相加并取模，然后输出即可。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 800;
const int mod = 1000000007;
char s[N];
stack<int> stk;
int rightt[N];
int f[N][N][5][5];
void dfs(int l, int r)
{
if (l + 1 == r)
{
f[l][r][0][1] = f[l][r][0][2] = f[l][r][1][0] = f[l][r][2][0] = 1;
return;
}
if (r == rightt[l])
{
dfs(l + 1, r - 1);
for (int i = 0; i <= 2; i ++)
for (int j = 0; j <= 2; j ++)
{
if (j != 1) f[l][r][0][1] += f[l + 1][r - 1][i][j], f[l][r][0][1] %= mod;
if (j != 2) f[l][r][0][2] += f[l + 1][r - 1][i][j], f[l][r][0][2] %= mod;
if (i != 1) f[l][r][1][0] += f[l + 1][r - 1][i][j], f[l][r][1][0] %= mod;
if (i != 2) f[l][r][2][0] += f[l + 1][r - 1][i][j], f[l][r][2][0] %= mod;
}
}
else
{
dfs(l, rightt[l]), dfs(rightt[l] + 1, r);
for (int i = 0; i <= 2; i ++)
for (int j = 0; j <= 2; j ++)
for (int p = 0; p <= 2; p ++)
for (int q= 0; q <= 2; q ++)
{
if (j == 1 && p == 1 || j == 2 && p == 2) continue;
f[l][r][i][q] += (f[l][rightt[l]][i][j] * f[rightt[l] + 1][r][p][q] % mod);
f[l][r][i][q] %= mod;
}
}
}
int main() {
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = 1; i <= n; i++)
{
if (s[i] == '(') stk.push(i);
else
{
rightt[i] = stk.top();
rightt[stk.top()] = i;
stk.pop();
}
}
dfs(1, n);
int res = 0;
for (int i = 0; i <= 2; i ++)
for (int j = 0; j <= 2; j ++)
res += f[1][n][i][j], res %= mod;
cout << res << endl;
return 0;
}