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。

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

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

转移的时候滚动一下。

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

 #include <bits/stdc++.h>

 using namespace std;

 #define LL long long

 const int valid[] = {,,,};

 const LL mod = ;

 const int root = ;

 char s[];

 vector <int> e[];

 stack <int> stk;

 LL f[][];

 int n, ret, tot;

 void dfs(int u){

     f[u][] = ;

     LL tmp[];

     for (int i = , flag = ; i < (int)e[u].size(); i++){

         int v = e[u][i];

         dfs(v);

         if (!flag){

             for (int tk = (f[u][] = ); tk < ; ++tk){

                 int k = valid[tk];

                 f[u][k] = f[v][k];

             }

             flag = ;

         }

         else{

             for (int j = ; j < ; ++j) tmp[j] = ;

             for (int j = ; j < ; ++j)

                 for (int tk = ; tk < ; ++tk){

                     int k = valid[tk];

                     int cl[] = {j / , j % }, cr[] = {k / , k % };

                     if (cl[] >  && cr[] >  && cl[] == cr[]) continue;

                     int p = cl[] *  + cr[];

                     (tmp[p] += 1LL * f[u][j] * f[v][k]) %= mod;

                 }

             for (int j = ; j < ; ++j) f[u][j] = tmp[j];

         }

     }

     if (u != root){

         for (int j = ; j < ; ++j) tmp[j] = ;

         for (int j = ; j < ; ++j)

             for (int tk = ; tk < ; ++tk){

                 int k = valid[tk];

                 int ci[] = {j / , j % }, co[] = {k / , k % };

                 if ((ci[] >  && co[] >  && ci[] == co[])

                 || (ci[] >  && co[] >  && ci[] == co[])) continue;

                 (tmp[k] +=f[u][j]) %= mod;

             }

         for (int j = ; j < ; ++j) f[u][j] = tmp[j];

     }

 }

 int main(){

     scanf("%s", s + );

     n = strlen(s + ); tot = ;

     s[] = '(', s[n + ] = ')';

     for (int i = ; s[i]; ++i){

         if (s[i] == '('){

             if (tot) e[stk.top()].push_back(tot);

             stk.push(tot++);

         }

         else stk.pop();

     }

     dfs(root);

     ret = ;

     for (int i = ; i < ; ++i) (ret += f[root][i]) %= mod;

     return  * printf("%d\n", ret);

 }

巴特西

Codeforces 149D Coloring Brackets（树型DP）

最新文章

热门文章