「POI2016 R2」口吃 Stutter 题解

题目理解

我们有两个序列 $A$ 和 $B$，需要找到它们的最长公共口吃子序列。口吃序列定义为由连续的成对相同元素组成的序列，例如 $[x,x,y,y,z,z]$，长度为偶数。

问题转化

设 $f[x][i]$ 表示匹配了 $x$ 对口吃对后，在 $A$ 中匹配到位置 $i$ 时，在 $B$ 中所需的最小位置。

我们需要找到最大的 $x$，使得存在长度为 $2x$ 的公共口吃序列。

关键观察

1. 口吃序列结构：口吃序列由若干对 $(p,p)$ 组成，每对的两个元素相同
2. 匹配顺序：在匹配时，$A$ 和 $B$ 中对应的口吃对必须保持相对顺序
3. 贪心匹配：对于每对 $(p,p)$，我们在 $B$ 中寻找最早的匹配位置

算法思路

预处理

1. 离散化：将 $A$ 和 $B$ 中的值映射到 $1$ 到 $k$ 的整数范围
2. 后继数组：
   • $na[i]$ 表示在 $A$ 中位置 $i$ 之后下一个与 $a[i]$ 相同的位置
   • $nb[i]$ 表示在 $B$ 中位置 $i$ 之后下一个与 $b[i]$ 相同的位置

动态规划

设 $f[x][i]$ 表示匹配了 $x$ 对后，在 $A$ 中匹配到位置 $i$ 时，在 $B$ 中所需的最小位置。

状态转移的核心思想：

• 从 $f[x-1][i']$ 出发，在 $A$ 中找下一对 $(p,p)$
• 在 $B$ 中找对应的 $(p,p)$ 对，且位置要晚于当前匹配位置

优化技巧

1. 滚动数组：由于 $f[x][i]$ 只依赖 $f[x-1][i']$，使用滚动数组优化空间
2. 贪心匹配：在 $B$ 中维护每个值的最早可用位置 $g[t]$
3. 单调性利用：利用 $f[x][i]$ 的单调性进行高效转移

算法流程

离散化处理

for (int i = 1; i <= n; i++)
    cin >> a[i], c[++k] = a[i];
for (int i = 1; i <= m; i++)
    cin >> b[i], c[++k] = b[i];

sort(c + 1, c + 1 + k);
k = unique(c + 1, c + 1 + k) - c - 1;

for (int i = 1; i <= n; i++)
    a[i] = lower_bound(c + 1, c + 1 + k, a[i]) - c;
for (int i = 1; i <= m; i++)
    b[i] = lower_bound(c + 1, c + 1 + k, b[i]) - c;

预处理后继位置

// A 的后继
for (int i = n; i; i--)
    na[i] = pre[a[i]], pre[a[i]] = i;

// B 的后继  
for (int i = 1; i <= k; i++) pre[i] = 0;
for (int i = m; i; i--)
    nb[i] = pre[b[i]], pre[b[i]] = i;

动态规划核心

for (int x = 1;; x++) {
    int cur = x & 1, last = 1 - cur;
    int j = m;
    
    // 初始化当前层
    for (int i = 0; i <= n; i++) f[cur][i] = INF;
    for (int t = 1; t <= k; t++) g[t] = INF;
    
    // DP 转移
    for (int i = 1; i <= n; i++) {
        // 维护 B 中的匹配信息
        while (f[last][i - 1] < j && j) {
            if (nb[j]) g[b[j]] = min(g[b[j]], nb[j]);
            j--;
        }
        
        // 状态转移
        if (na[i]) 
            f[cur][na[i]] = min(f[cur][na[i]], g[a[i]]);
        
        f[cur][i] = min(f[cur][i], f[cur][i - 1]);
    }
    
    // 检查是否能匹配 x 对
    if (f[cur][n] == INF) {
        cout << (x - 1) * 2;  // 输出最大口吃序列长度
        break;
    }
}

算法正确性

1. 贪心选择：每次选择 $B$ 中最早的匹配位置，保证不会错过最优解
2. 状态定义：$f[x][i]$ 精确记录了匹配 $x$ 对后所需的最小资源
3. 单调性：$f[x][i] \leq f[x][i+1]$，保证转移的正确性

时间复杂度

• 离散化：$O((n+m)\log(n+m))$
• 预处理：$O(n+m)$
• 动态规划：$O(k \cdot (n+m))$，其中 $k$ 是最大口吃对数

由于 $k \leq \min(n,m)/2$，且使用滚动数组和贪心优化，算法在数据范围内可行。

算法标签

• 动态规划
• 贪心算法
• 离散化

总结

该算法通过巧妙的动态规划状态设计和贪心匹配策略，高效地解决了最长公共口吃序列问题。核心在于将复杂的序列匹配问题转化为逐对匹配的过程，并通过维护最小位置信息来保证最优性。