本文共 2445 字，大约阅读时间需要 8 分钟。

题目大意：给你一个符合括号规则的字符串，现在要求你将这些括号染色，染色规则如下

1.一个括号要么被染成红色，要么被染成蓝色，要么不染 2.相邻的括号的颜色不能相同(可以同为无色) 3.成对的括号只能有一个被染色 问染色的方案数

解题思路：0表示不染，1表示红色，2表示蓝色

那么成对的括号只能符合:(0,1),(1,0),(0,2),(2,0)4个中的任意一个 接下来讨论如何染色 用dp[i][j][k][l]表示[i,j]区间，i染成k色，j染成l色的方案数 假设要染色的是[l,r]这个区间 1.如果l + 1 == r，表示这个括号是最内部的括号了 那么dp[l][r][0][1] = dp[l][r][1][0] = dp[l][r][0][2] = dp[l][r][2][0] = 1

2.如果l这个位置的括号和r这个位置的括号匹配，那么先递归染[l + 1, r - 1]

染完后可得转移方程 dp[l][r][i][j] += dp[l + 1][r - 1][k][l]其中k不能等于i，l不能等于j，因为要符合第2个规则

3.不符合情况1和情况2，那就先染[l, match[l]]和[match[l] + 1, r]这两个区间的括号，match[l]表示第l个括号的匹配括号所在位置

染完后得转移方程 dp[l][r][i][j] += dp[l][match[l]][i][k] * dp[match[l] + 1][r][q][j]，其中k == q时不能等于1或2，要满足第二个规则

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int N = 710;const int MOD = 1e9 + 7;typedef long long ll;char str[N];int match[N], num[N];ll dp[N][N][3][3];int len;void init() {    scanf("%s", str);    len = strlen(str);    int cnt = 0;    for (int i = 0; i < len; i++)        if (str[i] == ')')            match[num[--cnt]] = i;        else             num[cnt++] = i;}void dfs(int l, int r) {    //一对括号    if (l + 1 == r) {        dp[l][r][0][1] = 1;        dp[l][r][0][2] = 1;        dp[l][r][1][0] = 1;        dp[l][r][2][0] = 1;    }    else if (match[l] == r) {        dfs(l + 1, r - 1);        for (int i = 0; i < 3; i++)            for (int j = 0; j < 3; j++) {                if (j != 1) dp[l][r][0][1] += dp[l + 1][r - 1][i][j];                if (j != 2) dp[l][r][0][2] += dp[l + 1][r - 1][i][j];                if (i != 1) dp[l][r][1][0] += dp[l + 1][r - 1][i][j];                if (i != 2) dp[l][r][2][0] += dp[l + 1][r - 1][i][j];            }        dp[l][r][0][1] %= MOD;        dp[l][r][0][2] %= MOD;        dp[l][r][1][0] %= MOD;        dp[l][r][2][0] %= MOD;    }    else {        dfs(l, match[l]);        dfs(match[l] + 1, r);        for (int i = 0; i < 3; i++)            for (int j = 0; j < 3; j++)                for (int k = 0; k < 3; k++)                    for (int p = 0; p < 3; p++)                        if (!( (k == 1 && p == 1) || (k == 2 && p == 2)))                            dp[l][r][i][j] = (dp[l][r][i][j] + (dp[l][match[l]][i][k] * dp[match[l] + 1][r][p][j]) % MOD) % MOD;    }}void solve() {    dfs(0, len - 1);    ll ans = 0;    for (int i = 0; i < 3; i++)        for (int j = 0; j < 3; j++)            ans += dp[0][len - 1][i][j];    printf("%lld\n", ans % MOD);}int main() {    init();    solve();    return 0;}
     
    
   

转载地址：https://blog.csdn.net/L123012013048/article/details/48834219 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！