# 异星工厂：科技树——三状态动态规划

Codex（GPT-6）应用已有的三状态深度优先遍历与记忆化方法，沿依赖方向计算最早完成时刻。程序：[alternative-depth-first.cpp](alternative-depth-first.cpp)。共同建模与时刻最优性证明见[主解](solution.zh.md)。

## 沿依赖求值

忽略任一端点已完成的依赖。这次保存 $u\to v$ 表示“$u$ 依赖 $v$”，方向与队列方案相反。每个结点有三种状态：未访问、正在计算、已经完成计算。

从未访问结点开始，用显式帧保存当前结点及下一条依赖边。遇到未访问依赖，先压入其帧；该帧完成后，父帧再读它的结果。遇到已经完成的依赖，累积其完成时刻的最大值。所有依赖处理完时，再加自身耗时并标为已完成计算。

## 检测环与正确性

正在计算的结点恰好组成当前深度优先路径。若当前依赖指向一个正在计算的结点，就出现回到祖先的边，该边与路径构成环，立即输出 `bad idea` .反之，有向图无环时不会出现这种回边。

每个结点在所有依赖计算完后才定值，因此按照完成计算的次序归纳，其结果符合主解的最早完成时刻递推。已完成计算的结点可被多个后继复用，不会重复展开。显式帧与递归的进入、返回顺序相同。

## 复杂度与取舍

每个结点进入和退出各一次，每条边至多在进入子结点前和返回后访问各一次，时间 $O(n+m)$ .邻接表、状态、结果与显式栈合计空间 $O(n+m)$ .

它省去入度计数，却要维护三状态和栈帧。两种方法都在线性时间内完成；差别是遍历与状态组织，而不是渐进复杂度。帧退出后才给本结点加耗时，避免重复加值；结果使用 64 位整数。计时比较见[主解](solution.zh.md#验证与运行)。