# 从最优脚本到结构化分段：完整单元任务与题解

## 任务与统一约定

本任务使用四个对象：

1. 字符串 `CACTUS` 与 `CATCUS`，允许单位插入、删除、替换
2. 字符串 `ABCDA` 与 `BACDEA`，只允许单位插入、删除
3. 非负工作量 `(2,0,3,1,4,2,0,5,1,3,2,1)`，划分为四个非空连续批次，费用为每批总量的平方之和
4. 反例工作量 `(-1,-2,-2,2)`，划分为两段

字符串下标在程序里从零开始。分段状态 D[t][j] 表示前 j 项分成 t 段；切点 k 表示下一段从第 k+1 项开始。所有分段方法在同费时选最小 k。Myers 的等远起点选删除；完整编辑表的回溯则先对角、再删除、最后插入。Hirschberg 选择最左中线切点，不要求其脚本与完整表逐字一致。

下载同目录的 foundation-structured-dp-capstone.py，用 Python 3 直接运行：

```sh
python foundation-structured-dp-capstone.py results.json
```

只使用 Python 标准库，不读仓库、网络或其他数据文件。省略输出参数时，在当前目录生成 foundation-structured-dp-capstone-results.json。报告中的无穷写成字符串 `inf`，便于严格 JSON 解析。

## 第一部分：脚本必须能真正执行

### 1. 三种编辑操作的费用 2

CACTUS 与 CATCUS 的长度都为六。完整编辑表的右下角为 2，回溯得到：匹配 C，匹配 A，替换 C→T，替换 T→C，匹配 U，匹配 S。

直接应用得到目标串 CATCUS。下界也为 2：一次插删会改变长度，一次替换只改变一个位置，但两串有两个对应位置不同。因此这份脚本最优。

另有同费解释：删去第三个 C，再在 T 后插入 C。完整 DP 与 Hirschberg 可以选择不同脚本，但必须同时满足：

- 每次读到的源字符与脚本记录一致
- 源字符全部且仅被消耗一次
- 拼接生成字符恰为目标串
- 非匹配操作数为 2

脚本中的 `apply_ops` 完整检查这四项。不要用“操作后的绝对字符位置”混合解释对齐流，否则一次删除会使后续下标漂移。

### 2. Hirschberg 如何找回路径

除了上述同输入比较，脚本还给出 CABACDA→ABCDA 的完整中线追踪。第一次源串切在第三字符之后，目标切点从 0 到 5 的前向费用为 `(3,2,1,2,3,4)`，后向费用按原切点编号为 `(1,1,1,2,3,4)`，总和为 `(4,3,2,4,6,8)`。

唯一最小切点为 2，问题分解成 CAB→AB 与 ACDA→CDA。两块各删一个字符，总费用 2。源串长度比目标多二，也独立证明费用不能更低。

正常运行不保留中线历史，只用输入范围下标，不切片复制子串。选择切点后释放工作数组，再进入孩子。数组上界为常数倍短串长度；直接递归另占对数栈深。本例的数组上界是 18 个数，递归最大深度为 3。为教学开启 `trace=True` 后保存的数组历史是额外日志，不能同时算作节省空间的运行模式。

### 3. Myers 的费用 3 属于插删模型

ABCDA→BACDEA 的保留前沿依次为：

| d | k: 最远 x |
|---|---|
| 0 | 0:0 |
| 1 | -1:1，1:2 |
| 2 | -2:1，0:4，2:3 |
| 3 | -3:1，-1:5，此时到终点 |

回溯操作为插入 B、匹配 A、删除原 B、匹配 C 和 D、插入 E、匹配 A。依次改写 ABCDA→BABCDA→BACDA→BACDEA，总费用 3。

长度差为一，插删总数必须为奇数；若只做一次，就只能插入，而 ABCDA 不是 BACDEA 的子序列。因此费用至少三，脚本达到下界。单字符 A→B 在该模型费用为 2，而允许替换时费用为 1，这个测试能抓出混用模型的问题。

边界剪枝并不枚举所有恰 d 编辑可达状态。脚本特别记录 ab→baaa：第 1 层 k=1 的最远代表是 (2,1)，第 2 层 k=2 的删除越界，被剪去；直接删去 a,b 仍能到 (2,0)，但该较短状态的完成成本高两次，不影响最短终点。验收时应检查算法足以保留最优终点，不要断言剪枝后的前沿等于全部恰层可达集合。

边界处理还加入对角线退役：第一次到达右边或下边的端点照常留在当前前沿，供下一层执行合法出边，并保留全部回溯记录；后续层不再重新计算同一条对角线。若第 d₀ 层到达 (x,n)，删除余下源字符的总费用为 d₀+m−x；后来同对角线上的任意点，其完成费用至少为 d+m−x，严格更差。若直接完成时遇到此前退役的下一条对角线，那条线已以更低费用到达同一边界点，反而给出更便宜的完成方案，因此不会阻断最优脚本。

在退役前，一个内部端点的合法删除、插入两步会使同对角线的下一候选严格越过旧端点；若两个返回邻居都退役，该线也不会再出现。因此每条线的成功匹配扫描互不重叠，全部扫描为 O(N(D+1))，候选管理为 O((D+1)²)。原来的只剪越界版本会在 abbaaa→bba 的 k=1 上重复扫描尾段，还会在 abbabb→bbaa 上出现起点倒退；这两例连同三个空串边界已加入独立回归检查。有限检查验证实现，复杂度仍由上述计费论证给出。

## 第二部分：同一个分段问题的五份解

### 1. 基准递推与完整表

记前缀和

S = (0,2,2,5,6,10,12,12,17,18,21,23,24)。

令 D[0][0]=0，其余 D[0][j]=∞，并取

D[t][j] = min_{t-1≤k<j} {D[t-1][k] + (S[j]-S[k])²}。

每个状态取最左最优切点。各层有限的费用与切点为：

| 层 | 有效终点 j | 费用 | 最左切点 |
|---|---|---|---|
| 1 | 1..12 | 4,4,25,36,100,144,144,289,324,441,529,576 | 0,0,0,0,0,0,0,0,0,0,0,0 |
| 2 | 2..12 | 4,13,20,50,72,72,149,164,221,265,288 | 1,1,1,3,4,4,5,5,5,6,6 |
| 3 | 3..12 | 13,14,36,54,54,97,108,153,185,198 | 2,3,4,5,5,6,6,6,8,8 |
| 4 | 4..12 | 14,30,40,40,79,90,113,133,144 | 3,4,5,5,6,6,8,8,9 |

从 (t,j)=(4,12) 回溯到 k=9，再到 k=6、k=4，得到四段终点 4、6、9、12。每段总量都是 6，费用为 144。

独立下界：四段总量 u₁+u₂+u₃+u₄=24，平方和至少 24²/4=144，等号恰在四段总量相等时成立。因此这个分段不仅与五个程序一致，还有不依赖 DP 表的最优性证书。因为第七项是零，某些等价切法也同费；本任务固定最左回溯，选择第二个切点 6 而不是 7。

### 2. 分治删除候选的依据

四个合法格子上的候选成本差为

M[j,k]+M[j',k']-M[j,k']-M[j',k]
= -2(S[j']-S[j])(S[k']-S[k])≤0。

非负工作量使两个差都非负。用最左规则得到每层切点非降，于是求出中间行最优切点后，可以安全收紧左右子问题的候选区间。

第二层先求 j=7，扫描 k=1..6，费用为 104、104、74、72、104、144，选 k=4。左半终点的切点上界变为 4，右半下界变为 4。脚本在 `capstone.methods.divide.events` 中记录每一次实际扫描区间和选择。

### 3. SMAWK 还需要全单调性

SMAWK 的列淘汰要求保序子矩阵也保持最左极小列单调，不能只观察上一节的一串答案。有限合法部分具有 Monge 性；非法候选 k≥j 补 ∞ 后仍满足严格蕴含：若上行右列严格胜出，它必为合法有限项，左列也合法，下行继续允许两列，因此可用有限四点差传播严格优势。第一层只有 k=0 的上一层状态有限，其余候选无穷，也满足同一方向规则。

代码用严格小于弹列，同值保留更左列。结果报告另提供一个五行七列的完整削列/递归/插值事件例；其答案为 0、2、4、4、6。此小例调用接口 36 次，略多于朴素的 35 个格子，说明渐近界不保证每个小输入都减少常数。

### 4. 直线队列依靠两种单调性

展开平方可写成

D[t][j] = S[j]² + min_{k<j} {(-2S[k])·S[j] + D[t-1][k]+S[k]²}。

依次把候选 k 转成斜率 -2S[k]、截距 D[t-1][k]+S[k]² 的线，在 x=S[j] 查询。非负工作量让插入斜率非增、查询点非降。计算 j 前只加入新合法候选 k=j-1，跳过上层无穷状态。

相等前缀和会产生相等斜率，必须保留较小截距，再按较小 k 打破平局。三条线交于同一点时，中间线只有平局获胜的可能；因编号随插入递增，更早的第一条可负责此点，所以冗余判断可包含等号。代码另有共同交点测试验证此规则。

### 5. Li Chao 不要求输入顺序单调

预先把所有前缀和排序去重为离散查询域。每次插入沿树的一条路径，保留中点胜者，另一条线下沉到唯一可能翻盘的半边。查询比较整条根叶路径；结点中点胜者不保证是全树的全局胜者。

Li Chao 与队列使用相同的直线恒等式和同样的候选开放时机，但不要求斜率或查询点有序。于是它能继续处理第三部分的负工作量。

## 第三部分：让条件真的失效

对工作量 (-1,-2,-2,2)，S=(0,-1,-3,-5,-3)。第二层终点 2、3、4 的正确切点为 1、2、1，正确费用为 5、13、5。

分治先求 j=3 得到 k=2，若误以为切点单调，就把 j=4 的候选限制在 k≥2，返回 9，漏掉 k=1。此时 Monge 四点差中的前缀和差不能保证同号，数学前提已经失效。直线平方展开仍是代数恒等式，因此 Li Chao 仍得到 5。单调队列也不应强行运行：插入斜率与查询横坐标都不再满足接口约定，代码通过断言拒绝这种调用。

## 第四部分：区间根优化的独立核验

Knuth 不是上述分层递推的另一种实现。对有序键频率 (3,1,4,2)，区间费用为频率和，满足四点不等式与包含单调性。全区间最优根为编号 2，左子树以 0 为根、1 为其右孩子，右孩子为 3，总费用 17。

程序逐项比较完整枚举和 Knuth 根区间枚举的成本表与最左根表，示例候选数分别为 20 与 15。另穷举长度 1..6、频率来自 {0,1,2} 的全部 1092 组输入，涵盖大量平局。

矩阵链维数 (2,3,2,10,1) 是另一个边界检查：前三个矩阵最佳顶层切在第二个矩阵后，四个矩阵最佳顶层切在第一个矩阵后，次序倒退。它的乘法费用依赖切点，不能仅凭区间 DP 外观就使用 Knuth。

## 成本核算与验收

| 方法 | 主成本，单位为算术操作或表项求值 | 重建/存储注意事项 |
|---|---|---|
| 完整编辑表 | O(mn+m+n) | 完整表 O((m+1)(n+1))，脚本 O(m+n) |
| Hirschberg | O(mn+m+n) | 工作数组 O(min(m,n)+1)，另有对数栈及输出；展示日志额外计 |
| Myers 本实现 | O((N+1)(D+1)) | 保存各层回溯历史 O((D+1)²)，另有输出 O(N) |
| 朴素分段 DP | O(Kn²) | 两层值 O(n)；完整切点表 O(Kn) |
| 分治分段 | O(Kn log n) | 对数递归栈；完整切点表另计 |
| SMAWK 分段 | O(Kn) 次 O(1) 接口求值 | 每层工作列表线性；必须证明全单调 |
| 单调直线队列 | O(Kn) 次算术操作 | 每层线性空间；两种单调顺序都必需 |
| Li Chao 分段 | O(n log n) 预处理，加 O(Kn log n) 操作 | 坐标与结点 O(n)，另存切点表 |
| Knuth 区间 DP | O(n²) | 区间费用表和根表 O(n²) |

结果中的 `counts_by_layer` 是代码实际执行的计数，不是渐近式。前三种分段扫描记录 oracle_calls，队列和 Li Chao 记录线值/冗余比较，它们的单位不同；不据此制作未经归一化的性能排名。整数输入大时，平方、乘积、比较的位复杂度另计，Python 任意精度整数只消除了溢出风险，并没有让大整数算术变成免费。

最终自动验收包含：

- 961 对由 A、B 构成、长度 0..4 的短串：Hirschberg 对完整替换 DP，Myers 对独立插删 DP，并逐条应用脚本
- 120 组非负分段输入：五种方法全部表值及最左切点一致，并显式检查补无穷后的严格全单调条件
- 383 个满足严格全单调性的 2×3 小矩阵：SMAWK 对朴素最左极小值
- 1092 组非负搜索树频率：朴素区间 DP 对 Knuth，包含零频率平局
- 12760 次 Li Chao 查询：与全部已插入直线的朴素扫描一致
- 2000 次单调直线队列查询：与朴素线扫描一致，含相等斜率；另验共同交点的编号平局
- 明确的负负载反例、矩阵链反例、Myers 边界剪枝反例，以及五个检查退役、扫描不重叠和空串的回归实例

这些有限测试检验实现和例子；算法对任意合法输入的保证来自正文中的不变量、交换论证与摊还分析。