CF149D Coloring Brackets – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

比较容易看出区间 dp,设 \(f(l, r)\) 表示 \([l, r]\) 这一段括号串的染色方案数。

容易发现,转移会用到括号的匹配信息,因此我们先 \(\mathcal{O}(n)\) 预处理每个括号匹配的另一个括号的位置,第 \(x\) 个括号匹配的括号位置记作 \(p[x]\)

然后发现 \([l, r]\) 不是合法括号串对应的 \(f(l, r)\) 并没有意义,而且会带来转移上的麻烦;再加上 \(f(l, r)\) 的转移显然不可能用到一个 \(f(l’, r’)\) 使得 \([l’, r’]\) 不是合法括号串,因此我们初步考虑使用记忆化搜索实现区间 dp 的转移。这样以来,访问到的所有 \(f(l, r)\) 均代表 \([l, r]\) 是一个合法括号串,会减少很多麻烦。

然而,一个括号的染色状态会影响其他括号的染色状态,也就是染色上存在限制。一般奇怪的限制都考虑设入 dp 状态,因此设 \(f(l, r, p, q)\) 表示 \([l, r]\) 这段合法括号串,字符 \(l\) 的染色状态为 \(p\),字符 \(r\) 的染色状态为 \(q\) 的染色方案数。染色状态为 \(0\)\(1\)\(2\) 分别代表没有染色,染成了红色和染成了蓝色。其中 \(l, r\) 是阶段,\(p, q\) 是决策。


先考虑边界情况,因为一般较为简单,而且让人有成就感。

边界是 \(r – l +1 = 2\) 的情况,也就是只有简单的一对括号 \(\texttt{()}\),那么显然有:

\(f(l, r, 0, 1) = f(l, r, 0, 2) = f(l, r, 1, 0) = f(l, r, 2, 0) = 1\),其余均为 \(0\)

然后考虑一般,我们发现可以分为两种情况:\(p[l] = r\)\(p[l] \ne r\)


对于 \(p[l] = r\),首先还是只用讨论 \(f(l, r, 0, 1)\)\(f(l, r, 0, 2)\)\(f(l, r, 1, 0)\)\(f(l, r, 2, 0)\) 这四种情况,剩下五种情况仍然不合法,值为 \(0\)

显然此时相当于 \([l +1, r – 1]\) 这段合法括号序列外套一对括号,因此子阶段是 \(f(l + 1, r – 1, \cdots)\)

\([l, r]\)\([l + 1, r – 1]\) 之间的制约条件只剩下“相邻括号颜色不可相同”,我们枚举 \([l + 1, r – 1]\) 对应的颜色状态 \(p’\)\(q’\),当 \(p = 0 \lor p \ne p’\)\(q= 0 \lor q \ne q’\) 时,\(f(l +1, r – 1, p’, q’)\) 就可以对 \(f(l, r, p, q)\) 产生贡献。


对于 \(p[l] \ne r\),我们考虑子阶段 \(f(l, p[l], \cdots)\)\(f(p[l] + 1, r, \cdots)\),最后使用乘法原理统计答案即可。

具体来说,我们分别枚举 \(l\)\(p[l]\)\(p[l] + 1\)\(r\) 的颜色 \(a\)\(b\)\(c\)\(d\),当 \(b = 0 \lor b \ne c\) 时(相邻括号不同色),就可以用 \(f(l, p[l],a, b) \times f(p[l] + 1, r, c, d)\)\(f(l, r, a, d)\) 产生贡献。

至此区间 dp 的 \(\mathcal{O}(n^2)\) 做法已经说明完毕,一个细节是:事实上本题的搜索是不需要记忆化的,因为每个阶段 \(f(l, r, \cdots)\) 会非常自然地会只被访问一次。这一点直观上易于理解但难以言表,读者可以自己用一个括号串举例绘制阶段转移的过程,这不会耗费您多长时间,但会让您对这个状态转移的理解更深刻。


另外有一点,\(f(l, r, 0, 1) = f(l, r, 0, 2)\)\(f(l, r, 1, 0) = f(l, r, 2, 0)\)\(f(l, r, 1, 1) = f(l, r, 2, 2)\)\(f(l, r, 1, 2) = f(l, r, 2, 1)\)

将蓝红色简单互换就可以证明上面这四个等式。因此转移上可以偷懒(雾),等式中,计算出一个就能计算出另一个。

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2022-11-23 17:19:37 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2022-11-23 17:55:13
 */
#include <bits/stdc++.h>
#define int long long
inline std :: pair <std :: string, int> rest(bool space = true) {
    std :: string s;
    char ch = getchar();
    for (; !isgraph(ch); ch = getchar());
    for (; isgraph(ch); ch = getchar())
        s.push_back(ch);
    return {space ? " " + s : s, s.length()};
}

const int maxn = 705;
const int mod = (int)1e9 + 7;
std :: string s;

int f[maxn][maxn][3][3];
int p[maxn];

void sol(int l, int r) {
    if (r == l + 1) {
        f[l][r][0][1] = f[l][r][1][0] = f[l][r][0][2] = f[l][r][2][0] = 1;
        return ;
    }
    if (r == p[l]) {
        sol(l + 1, r - 1);
        f[l][r][0][1] = f[l][r][0][2] = (
            f[l + 1][r - 1][0][0] + f[l + 1][r - 1][0][2] + 
            f[l + 1][r - 1][1][0] + f[l + 1][r - 1][1][2] + 
            f[l + 1][r - 1][2][0] + f[l + 1][r - 1][2][2]) % mod;
        f[l][r][1][0] = f[l][r][2][0] = (
            f[l + 1][r - 1][0][0] + f[l + 1][r - 1][2][0] + 
            f[l + 1][r - 1][0][1] + f[l + 1][r - 1][2][1] + 
            f[l + 1][r - 1][0][2] + f[l + 1][r - 1][2][2]) % mod;
    } else {
        sol(l, p[l]);
        sol(p[l] + 1, r);
        
        for (int a = 0; a < 3; ++a)
        for (int b = 0; b < 3; ++b)
        for (int c = 0; c < 3; ++c)
        for (int d = 0; d < 3; ++d)
            if (!b || b != c)
                (f[l][r][a][d] += 
                (f[l][p[l]][a][b] * f[p[l] + 1][r][c][d])
                % mod) %= mod;
    }
}

signed main() {
    auto _ = rest(); s = _.first; int n = _.second;
    
    std :: stack <int> st;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '(')
            st.push(i);
        else {
            p[st.top()] = i;
            st.pop();
        }
    }

    sol(1, n);
    
    int ans = 0;
    for (int a = 0; a < 3; ++a)
        for (int b = 0; b < 3; ++b)
            (ans += f[1][n][a][b]) %= mod;
    printf("%lld\n", ans);
    return 0;
}

原文地址:http://www.cnblogs.com/crab-in-the-northeast/p/cf149d.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性