题目链接
分析： 区间dp。 开四维dp[l][r][x][y]，表示在区间[l, r]中，最左边涂x，最右边涂y，的可行状态数。 当l和r的括号配对的时候，可以从[l + 1, r - 1]推导出来。配对的括号要满足给定的要求。 当l和r的括号不配对的时候，那一定能把这个区间划分成两个配对的小区间，搜索配对的两个小区间。递归搜索两个子区间。这时候l和r的两个括号没必要满足颜色不同的要求。
代码：
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cstdlib> #include <vector> #include <queue> #include <stack> using namespace std; const int maxn = 705; const int mod = 1e9 + 7; stack<int> st; int match[maxn]; long long dp[maxn][maxn][3][3]; char s[maxn]; void dfs(int l, int r) { if (l >= r) return; if (l + 1 == r) { dp[l][r][1][0] = 1; dp[l][r][0][1] = 1; dp[l][r][2][0] = 1; dp[l][r][0][2] = 1; } else { if (match[l] == r) { dfs(l + 1, r - 1); for (int i = 0; i < 3; i ++) { for (int j = 0; j < 3; j ++) { if (i && j) continue; if (!(i == j)) for (int x = 0; x < 3; x ++) for (int y = 0; y < 3; y ++) { if (i && x == i) continue; if (j && y == j) continue; dp[l][r][i][j] = (dp[l][r][i][j] + dp[l + 1][r - 1][x][y]) % mod; } } } } else { int p = match[l]; dfs(l, p); dfs(p + 1, r); for (int a = 0; a < 3; a ++) for (int b = 0; b < 3; b ++) for (int c = 0; c < 3; c ++) for (int d = 0; d < 3; d ++) if (!((c == 1 && d == 1) || (c == 2 && d == 2))) dp[l][r][a][b] = (dp[l][r][a][b] + (dp[l][p][a][c] * dp[p + 1][r][d][b]) % mod) % mod; } } } int main(int argc, char const *argv[]) { scanf("%s", s); long len = strlen(s); memset(dp, 0, sizeof(dp)); for (int i = 0; i < len; i ++) { if (s[i] == '(') st.push(i); else { int x = st.top(); st.pop(); match[i] = x; match[x] = i; } } dfs(0, (int)len - 1); long long ans = 0; for (int i = 0; i < 3; i ++) for (int j = 0; j < 3; j ++) ans = (ans + dp[0][len - 1][i][j]) % mod; cout<<ans<<endl; }