CodeForces - 149D Coloring Brackets 详细题解（递归区间DP+dfs染色，好题）

Once Petya read a PRoblem about a bracket sequence. He gave it much thought but didn't find a solution. Today you will face it.

You are given string s. It represents a correct bracket sequence. A correct bracket sequence is the sequence of opening ("(") and closing (")") brackets, such that it is possible to obtain a correct mathematical expression from it, inserting numbers and Operators between the brackets. For example, such sequences as "(())()" and "()" are correct bracket sequences and such sequences as ")()" and "(()" are not.

In a correct bracket sequence each bracket corresponds to the matching bracket (an opening bracket corresponds to the matching closing bracket and vice versa). For example, in a bracket sequence shown of the figure below, the third bracket corresponds to the matching sixth one and the fifth bracket corresponds to the fourth one.

You are allowed to color some brackets in the bracket sequence so as all three conditions are fulfilled:

Find the number of different ways to color the bracket sequence. The ways should meet the above-given conditions. Two ways of coloring are considered different if they differ in the color of at least one bracket. As the result can be quite large, print it modulo1000000007 (109 + 7).

The first line contains the single string s (2 ≤ |s| ≤ 700) which represents a correct bracket sequence.

Print the only number — the number of ways to color the bracket sequence that meet the above given conditions modulo 1000000007(109 + 7).

(())output
12input
(()())output
40input
()output
4Note
Let's consider the first sample test. The bracket sequence from the sample can be colored, for example, as is shown on two figures below.
The two ways of coloring shown below are incorrect.
题目描述：
　　给一个合法的括号串，然后问这串括号有多少种涂色方案，当然啦！涂色是有限制的。
　　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;
细节：
如果l+1 == r 说明最里面那1对，一共就只有4种情况，同理如果两个括号相相匹也有4中情况，这就是为什么 这两种情况详细写出左右括号颜色的原因，一开始纠结为什么第三种情况不用考虑，直接枚举颜色就好了，万一两个一样的呢。。。 注意 第三种是不匹配的，所以根本不用管i，j是不是可能相同，因为可能是这种的（）（），然后dfs分别求出dp[l][k]，dp[k+1][r]所有可能，dp[l][k]肯定是匹配的所以他下层dfs肯定是进入第二种或者第一种情况，dp[k+1][r]却不一定是匹配的
这种递归的在区间dp里很常见，有深刻理解下，另一个递归的题目：
http://blog.csdn.net/QQ_34374664/article/details/59483996
深刻理解下递归
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int Mod = 1e9 + 7;const int maxn = 750;long long dp[maxn][maxn][5][5], temp[maxn], match[maxn];int len;char str[maxn];void get_match()  //这里就是最简单的括号匹配问题，用两个数组记录下，p作为“栈顶”{    len = strlen(str);    int p = 0;    for(int i = 0; i < len; i++)    {        if(str[i] == '(')            temp[p++] = i;        else        {            match[i] = temp[p-1];            match[temp[p-1]] = i;            p--;        }    }}void dfs(int l, int r){    if(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;        return ;    }    if(match[l] == r)    {        dfs(l+1, r-1);        for(int i = 0; i < 3; i++)            for(int j = 0; j < 3; j++)  //这两个括号是匹配的，所以他的两个括号不能同时染色，其实也就是4种情况了，一一枚举            {                if(i != 1)                    dp[l][r][1][0] = (dp[l][r][1][0]+dp[l+1][r-1][i][j])%Mod;                if(i != 2)                    dp[l][r][2][0] = (dp[l][r][2][0]+dp[l+1][r-1][i][j])%Mod;                if(j != 1)                    dp[l][r][0][1] = (dp[l][r][0][1]+dp[l+1][r-1][i][j])%Mod;                if(j != 2)                    dp[l][r][0][2] = (dp[l][r][0][2]+dp[l+1][r-1][i][j])%Mod;            }//        for(int i = 0; i < 3; i++)//            for(int j = 0; j < 3; j++)//                for(int x = 0; x < 3; x++)//                    for(int y = 0; y < 3; y++)//                    {//                        if(i && j) continue;//                        if(x == i && x) continue;//                        if(y == j && y) continue;//                        dp[l][r][i][j] = (dp[l][r][i][j] + dp[l+1][r-1][x][y])%Mod;//                    }    }    else    {        int k = match[l];        dfs(l, k);        dfs(k+1, r);        for(int i = 0; i < 3; i++)            for(int j = 0; j < 3; j++)                for(int x = 0; x < 3; x++)                    for(int y = 0; y < 3; y++)                    {                        if(x == y && x != 0) continue;                        dp[l][r][i][j] = (dp[l][r][i][j] + dp[l][k][i][x]*dp[k+1][r][y][j])%Mod;  //不匹配，括号颜色不必保证一个不染色，保证相邻不重复就好了                    }    }}int main(){    scanf("%s", str);    get_match();    dfs(0, 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;  //枚举所有染色可能性，因为最开始的不一定左右匹配        }    printf("%lld/n", ans);    return 0;}