「Genotype」题解

问题分析

这是一个文法推导问题：给定一组产生式规则 $X \rightarrow YZ$，其中 $X, Y, Z$ 都是大写字母（基因），需要判断给定的字符串能否由这些规则从起始符号 $S$ 推导出来，并求最少需要多少个 $S$。

关键点：

• 每个产生式规则将一个基因分裂成两个基因
• 起始符号是 $S$（特种基因）
• 目标字符串由大写字母组成，长度不超过100
• 需要求最少使用多少个 $S$ 才能产生目标字符串

问题转化

这实际上是一个上下文无关文法（CFG）的最优解析问题。我们可以将其转化为一个区间DP问题。

设目标字符串为 $s[1..m]$，长度为 $m$。

状态定义

定义 $dp[i][j][c]$ 表示：字符串 $s[i..j]$（子串）能否由单个基因 $c$ 推导出来。

但我们需要求的是最少 $S$ 的数量，所以更好的定义是： 定义 $f[i][j]$ 表示：生成子串 $s[i..j]$ 所需的最少 $S$ 的数量。如果不能生成，则 $f[i][j] = \infty$。

状态转移

对于子串 $s[i..j]$，有两种生成方式：

1. 直接生成：如果存在规则 $c \rightarrow s[i]s[i+1]...s[j]$ 对应的两个字符（注意规则是分裂成两个基因，不是多个），但这里的 $s[i..j]$ 可能很长，所以不能直接匹配。我们需要将 $s[i..j]$ 分解为两部分。

2. 分裂生成：

   • 将 $s[i..j]$ 在某个位置 $k$ 切分为两部分：$s[i..k]$ 和 $s[k+1..j]$
   • 如果存在规则 $c \rightarrow XY$，且 $s[i..k]$ 可由 $X$ 生成，$s[k+1..j]$ 可由 $Y$ 生成
   • 那么 $c$ 就可以生成 $s[i..j]$

算法框架

我们实际上需要两个DP表：

1. 生成表 $can[i][j][c]$：布尔值，表示子串 $s[i..j]$ 能否由单个基因 $c$ 生成。
2. 计数表 $cnt[i][j]$：生成子串 $s[i..j]$ 所需的最少 $S$ 数量。

步骤1：计算 $can[i][j][c]$

初始化：

• 对于每个位置 $i$，$can[i][i][s[i]] = true$（单个字符可以由对应的基因直接生成）

状态转移： 对于长度 $len = 2$ 到 $m$： 对于起始位置 $i = 1$ 到 $m-len+1$： 设 $j = i+len-1$ 对于每个分割点 $k = i$ 到 $j-1$： 对于每条规则 $c \rightarrow XY$： 如果 $can[i][k][X] \land can[k+1][j][Y]$，则 $can[i][j][c] = true$

时间复杂度：$O(m^3 \times R)$，其中 $R$ 是规则数，$m \leq 100$，最坏 $100^3 \times 10000 = 10^{10}$，太大！

优化

我们需要优化状态转移。观察到：

• 规则只有 $26 \times 26 \times 26 = 17576$ 种可能，但实际上最多只有 $n=10000$ 条规则
• 对于固定的 $i, k, j$，我们可以先计算哪些基因可以生成 $s[i..k]$，哪些可以生成 $s[k+1..j]$，然后查看规则表

更好的方法是：

1. 将规则组织成：对于每对 $(X, Y)$，记录所有能生成 $XY$ 的基因 $c$
2. 这样转移时，对于 $can[i][k][X]$ 和 $can[k+1][j][Y]$，我们可以直接得到 $c$

步骤2：计算 $cnt[i][j]$

初始化：

• $cnt[i][i] = 1$ 如果 $s[i]$ 可以由 $S$ 生成（即 $can[i][i][S] = true$），否则为 $\infty$

状态转移： $cnt[i][j] = \min$

1. 直接使用一个 $S$ 生成整个子串：如果 $can[i][j][S]$ 为真，则 $cnt[i][j] = 1$
2. 将子串分割：$cnt[i][j] = \min_{k=i}^{j-1} (cnt[i][k] + cnt[k+1][j])$

最终答案：$cnt[1][m]$

算法流程

预处理规则

1. 读取所有规则 $c \rightarrow XY$
2. 建立规则表 $rules[X][Y]$，存储所有能生成 $XY$ 的基因 $c$ 的列表

对每个查询字符串 $s$（长度 $m$）

阶段1：计算 $can$ 表

// 初始化
for i = 1 to m:
    for each c in ['A'..'Z']:
        can[i][i][c] = (s[i] == c)

// DP
for len = 2 to m:
    for i = 1 to m-len+1:
        j = i+len-1
        for k = i to j-1:
            // 获取所有能生成 s[i..k] 的基因集合 set1
            // 获取所有能生成 s[k+1..j] 的基因集合 set2
            for each X in set1:
                for each Y in set2:
                    for each c in rules[X][Y]:
                        can[i][j][c] = true

阶段2：计算 $cnt$ 表

// 初始化
for i = 1 to m:
    if can[i][i]['S']:
        cnt[i][i] = 1
    else:
        cnt[i][i] = INF

// DP
for len = 2 to m:
    for i = 1 to m-len+1:
        j = i+len-1
        
        // 方法1：直接用一个S生成
        if can[i][j]['S']:
            cnt[i][j] = 1
        else:
            cnt[i][j] = INF
            
        // 方法2：分割
        for k = i to j-1:
            cnt[i][j] = min(cnt[i][j], cnt[i][k] + cnt[k+1][j])

输出结果

• 如果 $cnt[1][m] = \infty$，输出 "NIE"
• 否则输出 $cnt[1][m]$

复杂度分析

• 对于每个查询字符串（长度 $m \leq 100$）：
  • 阶段1：$O(m^3 \times 26^2)$，但实际中基因集合很小
  • 阶段2：$O(m^3)$
  • 总复杂度：$O(m^3)$，对于 $m=100$，$100^3 = 10^6$ 可接受
• 查询数 $k \leq 10000$，但每个字符串独立处理
• 总复杂度：$O(k \cdot m^3)$，最坏 $10000 \times 10^6 = 10^{10}$，可能过大！

进一步优化

实际上，$m \leq 100$，$m^3 = 10^6$，$k=10000$ 时，$10^{10}$ 确实太大。需要优化：

优化1：预处理规则矩阵

• 建立 $26 \times 26$ 的矩阵，每个元素是一个位集（26位），表示能生成对应基因对的基因集合
• 这样可以在 $O(1)$ 时间内检查规则

优化2：使用位运算优化 $can$ 表

• $can[i][j]$ 可以是一个26位的位集，表示哪些基因能生成子串 $s[i..j]$
• 转移时：$can[i][j] |= rules[can[i][k]][can[k+1][j]]$
• 这里 $rules$ 需要支持位集输入输出

优化3：记忆化搜索 + 剪枝

• 使用记忆化搜索避免重复计算
• 当 $cnt[i][j]$ 已经为1时（直接由S生成），不需要进一步分割

优化4：限制查询字符串长度

• 题目说最多100个字母，但实际可能更短
• 可以统计实际的最大长度

最终算法

使用区间DP + 位运算优化：

1. 预处理规则为位集形式
2. 对每个查询：
   • 计算 $can[i][j]$（位集）
   • 计算 $cnt[i][j]$
3. 输出结果

特殊情况处理

1. 空字符串：题目没说，但长度为0时应该输出0（不过题目说最少1个字母）
2. 起始符号S：注意规则中可能有其他基因也能生成子串，但我们关心的是最少S的数量
3. 无法生成：如果 $cnt[1][m] = \infty$，输出 "NIE"

总结

本题是一个经典的文法解析问题，通过区间DP求解。关键点：

1. 将问题转化为区间DP
2. 使用两个DP表：一个判断能否生成，一个计算最少S的数量
3. 使用位运算优化规则匹配
4. 注意时间复杂度优化，因为查询数可能很多