【题意】：给出一个长度为n的括号序列，括号满足两两匹配。
给出三个条件：
1.每个括号可以不染色，染蓝色或者染红色；
2.匹配的括号对有且仅有一个染色；
3.相邻的括号不能染相同的颜色。
问，满足以上三个条件的染色方案有多少种。
【题解】：好明显的dp题，因为一般这种求方案数的题目如果用纯数学知识来解是解不出的，而且限制条件一大堆。
设状态dp[l][r][c1][c2]表示[l,r]之间且l染成c1,r染成c2的合法方案数。
然后转移要分两种情况讨论：1.l与r匹配；2.l与r不匹配
转移就是运用乘法原理，要先预处理括号的匹配情况。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "stack"
13 using namespace std;
14 #define pb push_back
15 #define lc(x) (x << 1)
16 #define rc(x) (x << 1 | 1)
17 #define lowbit(x) (x & (-x))
18 #define ll long long
19 #define MAX 710
20 const int MOD = 1000000007;
21 string str;
22 ll dp[MAX][MAX][3][3];
23 int mat[MAX];
24 int s[MAX], top;
25
26 void pretreatment() {
27 top = 0;
28 for(int i = 0; i < str.length(); i++) {
29 if(str[i] == '(') s[top++] = i;
30 else mat[s[--top]] = i;
31 }
32 }
33
34 bool check(int a, int b) {
35 if(a == 0 || b == 0 || a != b) return true;
36 return false;
37 }
38
39 ll func(int l, int r, int c1, int c2) {
40 if(dp[l][r][c1][c2] != -1) return dp[l][r][c1][c2];
41 ll res = 0;
42 if(mat[l] == r) {
43 if((c1 == 0) ^ (c2 == 0)) {
44 if(l + 1 == r) return dp[l][r][c1][c2] = 1;
45 for(int i = 0; i < 3; i++) {
46 for(int j = 0; j < 3; j++) {
47 if(check(c1, i) && check(j, c2)) {
48 res += func(l + 1, r - 1, i, j);
49 }
50 }
51 }
52 } else return dp[l][r][c1][c2] = 0;
53 } else {
54 for(int i = 0; i < 3; i++) {
55 for(int j = 0; j < 3; j++) {
56 if(check(i, j))
57 res += func(l, mat[l], c1, i) * func(mat[l] + 1, r, j, c2);
58 }
59 }
60 }
61 return dp[l][r][c1][c2] = res % MOD;
62 }
63
64 int main() {
65 while(cin >> str) {
66 pretreatment();
67 memset(dp, -1, sizeof(dp));
68 ll ans = 0;
69 for(int i = 0; i < 3; i++)
70 for(int j = 0; j < 3; j++)
71 ans += func(0, str.length() - 1, i, j);
72 cout << ans % MOD << endl;
73 }
74 return 0;
75 }
76