题目重点：把三个工厂枚举提升为分层动态规划，再用是否已经跳过和上个选中位置解决恰跳一层。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 每道工序有若干选项 (生产价, 铁轨位置)，未跳过时每层必须选一个；总价为生产价之和加相邻选中工厂位置差绝对值。
- 训练版跳过的是一道工序，而不是同一层内的一个选项；恰好跳过一次，跳过后的前后两家直接承担位置差。若题面定义运输链断开，转移式要改。
- 价钱为非负整数，空选项层若不能跳过则无解；N=0 时非跳过返回 0、恰跳返回无解。
解题路线
- 无距离时各层分别选 min 报价，O(总选项数)；三层有距离时三重枚举可作正确性基线，复杂度 O(k1k2k3)。
- 任意 N 层定义 dp[i][j] 为处理到第 i 层且选择选项 j 的最低价：cost[i][j]+min_k(dp[i−1][k]+|pos[i][j]−pos[i−1][k]|)。记录前驱可恢复完整选择，滚动数组只保留最优价。
- 恰跳一层时，状态保留 (是否已跳, 上一个被选位置) 的最低代价。选择当前选项就加报价和与上个位置的距离；若尚未跳过，可跳过本层并保留上个位置，下一层直接与它相连。末尾只接受已跳过状态。
- 校验空层、只一层、首/末层跳过、负坐标、相同位置和远距离低报价等用例；生产价可能大于当前最优也不能仅凭局部报价剪枝，除非已证明所有剩余成本非负且当前下界成立。
手动走一遍
训练例两层：A 有 (5,0)、(2,10)，B 有 (3,1)、(1,9)。选 A(5,0)+B(3,1) 总价 9；选 A(2,10)+B(1,9) 总价 4，为最优。若中间再插一层且恰跳它，代码必须直接计算 A 与 B 之间的距离，而非把运输费重置为 0。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from __future__ import annotations
def minimum_factory_cost(
stages: list[list[tuple[int, int]]], *, skip_exactly_one: bool = False
) -> int | None:
"""Each (production_cost, rail_position) is one factory option.
If a stage is skipped, transport connects the nearest selected stages.
Return None when no valid selection exists. All costs are nonnegative.
"""
if not stages:
return None if skip_exactly_one else 0
# (skips_used, last_selected_position) -> minimum total cost
states: dict[tuple[int, int | None], int] = {(0, None): 0}
for options in stages:
next_states: dict[tuple[int, int | None], int] = {}
for (skips, previous_position), prior_cost in states.items():
if skip_exactly_one and skips == 0:
key = (1, previous_position)
next_states[key] = min(next_states.get(key, float("inf")), prior_cost)
for production_cost, position in options:
if production_cost < 0:
raise ValueError("production cost must be nonnegative")
transport = 0 if previous_position is None else abs(position - previous_position)
key = (skips, position)
candidate = prior_cost + production_cost + transport
next_states[key] = min(next_states.get(key, float("inf")), candidate)
states = next_states
if not states:
return None
target_skips = 1 if skip_exactly_one else 0
answer = [cost for (skips, _), cost in states.items() if skips == target_skips]
return min(answer) if answer else None
复杂度
N 层每层最多 K 个不同位置时，普通 DP O(NK²) 时间、O(K) 价钱空间；带恰跳状态时最坏 O(NK²) 时间、O(K) 滚动状态。若位置是大整数，Python 任意精度；固定宽度语言要防成本累加溢出。
易错点与追问
容易失分的边界
- 只把三重循环改成递归枚举，N 增加后仍指数增长。
- 跳层时把上一个位置清空，遗漏跨越该层的铁路费用。
- 把跳过一层误解成仅不选择某个工厂候选。
- 没有区分无解与真实零成本。
继续深挖
- 位置已排序时，如何用左右扫描的 min(dp[k]−pos[k]) 和 min(dp[k]+pos[k]) 把每层降为 O(K log K) 或 O(K)？
- 若恰跳 S 层，状态和复杂度如何扩展？
- 若运输费不是绝对距离而是非线性费率，哪些优化失效？
