P8986 [北大集训 2021] 基因编辑

CTT2021 D1T3

人类目前已经研究出了多种基因编辑技术，其中最传统的一种技术需要用到“限制性核酸内切酶”（简称限制酶）。这种酶能够识别特定的核苷酸序列，并在指定的位点上切割连接相邻核苷酸的磷酸二酯键，产生被称为“末端”的序列切口。只有相匹配的末端才能用 DNA 连接酶进行连接。 假设现在要用基因片段 $A$ 去替换某一载体 $V$ 上的基因片段 $B$。在使用限制酶的编辑技术中，通常需要进行以下操作： 1. 在基因 $A$ 的两端各选择一种限制酶识别位点。这两处识别位点在基因 $B$ 的两端也应当相应存在。 2. 用所选择的识别位点对应的限制酶对基因 $A$ 进行处理，使得其两端产生相应的末端。将处理后的基因 $A$ 提纯。 3. 用同样的限制酶切断载体 $V$ 上的识别位点，使得基因 $B$ 与载体 $V$ 断开。纯化出去除了基因 $B$ 的载体 $V'$。 4. 将载体 $V'$ 与基因 $A$ 混合，并在 DNA 连接酶的帮助下将断开的磷酸二酯键重新接上。 值得一提的是，如果两处识别位点断开后产生了相同的末端，那么在第 4 步中载体 $V'$ 有可能单独连接起来，产生了不包含基因 $A$ 或 $B$ 的载体；也有可能基因 $A$ 反向接入 $V'$，同样产生错误的载体。因此，在实际运用中，通常选取产生不同末端的限制酶对基因 $A$ 和载体 $V$ 进行处理。 公元 3032 年，人类发现了一种掌握了基因编辑技术的外星文明 HD1048576d。当然，这种基因编辑的技术仅限于居住在 HD1048576d 这颗行星上的外星生物的基因。我们人类掌握的基因编辑技术可识别的最小单位是 DNA 序列上的单个碱基，而外星文明的基因编辑技术可识别的最小单位是其基因序列上的单个 noicleobase。出于方便起见，我们可以将单个 noicleobase 用从 $1$ 开始的正整数表示，那么一段外星生命的基因序列就可以被表示成相应的正整数序列。 对于一段长度为 $n$ 的外星生命的基因序列（不妨记其正整数表示为 $s_1, s_2, \cdots, s_n$），外星文明 HD1048576d 的基因编辑过程如下： 1. 选择一段要编辑的区域 $[l, r]$，即原位替换原序列中 $s_l, s_{l+1}, \cdots, s_r$ 这部分子序列； 2. 挑选一对跨过待替换区域的下标 $(i, j)$（即 $1\le i

无

无

最优方案为切割 `1 4 7 4 8 3`。可以证明，没有比这更优秀的满足技术限制的切割方案。 一种比该方案切割长度更短的方案是 `4 7 4 8 3`，但是在这种方案中特异性识别工具可能会断开 `4 8 3`，从而导致产生的目标基因序列出现意外的突变，因此这种切割方案不满足技术限制。 --- 对于 $100\%$ 的数据，保证 $3\le n \le 10^6$，$\forall 1\le i\le n, 1\le s_i\le 10^6$，且 $1