Codeforces 149D Coloring Brackets（树型DP）

题目链接 Coloring Brackets

考虑树型DP。（我参考了Q巨的代码还是略不理解……）

首先在序列的最外面加一对括号。预处理出DFS树。

每个点有9中状态。假设0位不涂色，1为涂红色，2为涂蓝色。

0：0 0

1：0 1

2：0 2

3：1 0

4：1 1

5：1 2

6：2 0

7：2 1

8：2 2

其中1、2、3、6为有效的状态。

DP的时候如果当前括号下没有子括号那么这个状态方案数为1。

先处理出第一对括号。然后处理接下来的括号。

拼接的时候如果出现（）（）中间两个括号同时染色并且颜色相同那么该状态不合法，跳过。

转移的时候滚动一下。

如果当前节点不是根的话那么最后处理的时候只保留合法的状态。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define LL long long
 6 
 7 const int valid[4] = {1,2,3,6};
 8 const LL mod = 1000000007;
 9 const int root = 0;
10 
11 char s[705];
12 vector <int> e[705];
13 stack <int> stk;
14 LL f[705][9];
15 int n, ret, tot;
16 
17 void dfs(int u){
18     f[u][0] = 1;
19     LL tmp[9];
20     for (int i = 0, flag = 0; i < (int)e[u].size(); i++){
21         int v = e[u][i];
22         dfs(v);
23         if (!flag){
24             for (int tk = (f[u][0] = 0); tk < 4; ++tk){
25                 int k = valid[tk];
26                 f[u][k] = f[v][k];
27             }
28 
29             flag = 1;
30         }
31 
32         else{
33             for (int j = 0; j < 9; ++j) tmp[j] = 0;
34             for (int j = 0; j < 9; ++j)
35                 for (int tk = 0; tk < 4; ++tk){
36                     int k = valid[tk];
37                     int cl[2] = {j / 3, j % 3}, cr[2] = {k / 3, k % 3};
38                     if (cl[1] > 0 && cr[0] > 0 && cl[1] == cr[0]) continue;
39                     int p = cl[0] * 3 + cr[1];
40                     (tmp[p] += 1LL * f[u][j] * f[v][k]) %= mod;
41                 }
42 
43             for (int j = 0; j < 9; ++j) f[u][j] = tmp[j];
44         }
45     }
46 
47     if (u != root){
48         for (int j = 0; j < 9; ++j) tmp[j] = 0;
49         for (int j = 0; j < 9; ++j)
50             for (int tk = 0; tk < 4; ++tk){
51                 int k = valid[tk];
52                 int ci[2] = {j / 3, j % 3}, co[2] = {k / 3, k % 3};
53                 if ((ci[0] > 0 && co[0] > 0 && ci[0] == co[0])
54                 || (ci[1] > 0 && co[1] > 0 && ci[1] == co[1])) continue;
55                 (tmp[k] +=f[u][j]) %= mod;
56             }
57         for (int j = 0; j < 9; ++j) f[u][j] = tmp[j];
58     }
59 }
60 
61 
62 int main(){
63 
64     scanf("%s", s + 1);
65     n = strlen(s + 1); tot = 0;
66     s[0] = '(', s[n + 1] = ')';
67     for (int i = 0; s[i]; ++i){
68         if (s[i] == '('){
69             if (tot) e[stk.top()].push_back(tot);
70             stk.push(tot++);
71         }
72 
73         else stk.pop();
74     }
75 
76     dfs(root);
77     ret = 0;
78     for (int i = 0; i < 9; ++i) (ret += f[root][i]) %= mod;
79     return 0 * printf("%d
", ret);
80 }

Codeforces 149D Coloring Brackets（树型DP）

相关推荐