codeforces 149D Coloring Brackets (区间DP + dfs)

题目链接：

题目描述：

　　给一个合法的括号串，然后问这串括号有多少种涂色方案，当然啦！涂色是有限制的。

　　1,每个括号只有三种选择：涂红色，涂蓝色，不涂色。

　　2,每对括号有且仅有其中一个被涂色。

　　3,相邻的括号不能涂相同的颜色，但是相邻的括号可以同时不涂色。

解题思路：

　　这个题目的确是一个好题，无奈我太蠢，读错题意。以为(())这样的括号序列在涂色的时候，第一个括号与第三个括号也可以看做是一对。这样的话还要统计合法的括号匹配数目，还要计算涂色的方案。然后想了好久好久。最后发现并不是这样的，给出的括号序列，括号的匹配都是固定的，也就是说只需要给这些固定匹配的括号按照上面限制涂色就好啦。

　　可以定义 dp[l][r][x][y] 表示区间 [l, r] 在左端点涂x色，右端点涂y色的情况下的方案数。其中0代表不涂色， 1代表涂红色， 2代表涂蓝色。

　　窝们可以把括号序列可以分为两类分别进行状态转移：

　　括号套括号，状态转移是：dp[l][r][x][y] += dp[l+1][r-1][x'][y'] (0<=x'<3, x'!=x, 0<=y'<3, y!=y')

　　多个匹配串连起来，转台转移是：dp[l][r][x][y] += dp[l][nu][x'][y'] * dp[nu][r][x''][y''] (nu是l对应的另一边括号)

　　当l+1 == r的时候有：dp[l][r][0][1] = 1;　　dp[l][r][1][0] = 1;

　　　　　　　　　　　　 dp[l][r][0][2] = 1;　　dp[l][r][2][0] = 1;

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef __int64 LL;

 const LL mod = ;

 const LL maxn = ;

 LL dp[maxn][maxn][][], match[maxn], tep[maxn];

 void get_macth (char a[])

 {

     int p = ;

     for (int i=; a[i]; i++)

     {

         if (a[i] == '(')

             tep[p ++] = i;

         else

         {

             match[i] = tep[p-];

             match[tep[p-]] = i;

             p --;

         }

     }

 }

 void dfs (int l, int r)

 {

     if (l +  == r)

     {

         dp[l][r][][] = ;

         dp[l][r][][] = ;

         dp[l][r][][] = ;

         dp[l][r][][] = ;

         return ;

     }

     else if (match[l] == r)

     {

         dfs (l+, r-);

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

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

             {

                 if (j != )

                     dp[l][r][][] = (dp[l][r][][] + dp[l+][r-][i][j]) % mod;

                 if (i != )

                     dp[l][r][][] = (dp[l][r][][] + dp[l+][r-][i][j]) % mod;

                 if (j != )

                     dp[l][r][][] = (dp[l][r][][] + dp[l+][r-][i][j]) % mod;

                 if (i != )

                     dp[l][r][][] = (dp[l][r][][] + dp[l+][r-][i][j]) % mod;

             }

         return ;

     }

     else

     {

         int nu = match[l];

         dfs (l, nu);

         dfs (nu+, r);

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

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

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

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

                         if (!(x==&&y== || x==&&y==))

                         dp[l][r][i][j] = (dp[l][r][i][j] + dp[l][nu][i][x]*dp[nu+][r][y][j]) % mod;

     }

 }

 int main ()

 {

     char s[maxn];

     while (scanf ("%s", s) != EOF)

     {

         memset(dp, , sizeof(dp));

         int len = strlen (s);

         get_macth (s);

         dfs (, len-);

         LL ans = ;

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

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

                 ans = (ans + dp[][len-][i][j]) % mod;

         printf ("%I64d\n", ans);

     }

     return ;

 }

巴特西

codeforces 149D Coloring Brackets (区间DP + dfs)

最新文章

热门文章