「KTSC 2022 R2」彩色括号序列 题解

题目分析

本题要求统计给定彩色括号序列中所有五彩缤纷括号子序列的数量。五彩缤纷的括号序列需要满足：

1. 括号形式正确：忽略颜色后是合法的括号序列
2. 相邻括号颜色不同：序列中任意相邻两个括号颜色不同
3. 配对括号颜色不同：相互匹配的左右括号颜色不同

核心思路

使用区间DP来统计所有合法的彩色括号子序列。定义状态：

• f[l][r]：区间 [l, r] 作为一个完整匹配的括号序列的方案数
• g[l][r]：区间 [l, r] 作为一个任意合法括号序列的方案数

关键DP转移

void dp() {
    for (int len = 2; len <= n; ++len) {
        // 使用二维差分数组优化区间更新
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            
            if (p[l] > 0 || p[r] < 0) continue;
            
            // 基础情况：直接匹配左右括号
            if (p[l] != -p[r]) f[l][r] += 1;
            
            g[l][r] = f[l][r];
            
            // 复杂转移：考虑中间的分割点
            for (int i = l + 1; i + 1 < r; ++i) {
                if (p[i] < 0 || p[i] == -p[l]) continue;
                // 组合不同区间的方案数
                g[l][r] += f[l][i] * (总方案 - 颜色冲突的方案);
            }
            
            // 更新差分数组
            deltaf[pre[l] + 1][r + 1] += g[l][r].val();
            // ... 其他差分更新
        }
    }
}

算法实现细节

颜色冲突处理

使用预处理数组来快速处理颜色冲突：

// 预处理相同颜色的最近位置
map<int, int> cur;
for (int i = 1; i <= n; ++i) {
    pre[i] = cur[p[i]];  // 前一个相同颜色的位置
    cur[p[i]] = i;
}

优化技巧

$1.$ 二维差分数组：避免重复计算，优化区间更新 $2.$ 颜色桶：快速统计特定颜色的方案数 $3.$ 提前剪枝：跳过不合法的括号对

完整解法

int count(vector<int> P) {
    n = P.size();
    
    // 预处理颜色位置信息
    for (int i = 1; i <= n; ++i) {
        p[i] = P[i - 1];
        pre[i] = cur[p[i]];
        cur[p[i]] = i;
    }
    
    // 执行DP计算
    dp();
    
    // 统计所有完整序列
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (p[i] < 0 && !pre[i]) {  // 左括号且无前驱相同颜色
            for (int j = n; j > i; --j) {
                if (p[j] > 0 && nxt[j] == n + 1) {  // 右括号且无后继相同颜色
                    ans += g[i][j];
                }
            }
        }
    }
    
    return ans.val();
}

复杂度分析

• 时间复杂度：$O(N^3)$，其中 $N \leq 700$，在可接受范围内
• 空间复杂度：$O(N^2)$，用于存储DP状态

总结

本题通过精心设计的区间DP，结合颜色冲突处理和优化技巧，高效地统计了所有合法的彩色括号子序列。关键在于：

$1.$ 分离 f 和 g 的状态定义 $2.$ 利用预处理信息快速判断颜色冲突 $3.$ 使用差分数组优化状态转移

这种区间DP+颜色约束的组合方法在处理复杂的括号序列计数问题时非常有效。