最优二叉检索树: 题解¶
方法与贡献¶
出题人解法是枚举根的区间动态规划，并在代价相同时选较小的根。Codex（GPT-6）应用 Knuth 的最优搜索树优化，并用显式栈重建先序遍历。std.cpp 为首选；完整枚举的 alternative.cpp 与题解保留为便于独立理解的方案，支持本题全部范围。
出题人解法：区间动态规划¶
搜索树的任意子树恰好包含一个连续编号区间。令 \(D(l,r)\) 为该区间单独成树、根深度为一时的最小代价，空区间为零。令 \(W(l,r)=\sum_{i=l}^r f_i\) .枚举根 \(k\) 时，左右子树的所有深度都要增加一，因此
按区间长度递增计算。所有合法树都有唯一的根，两个子树又必须独立最优，故递推完整且不遗漏更优解。
令 \(R(l,r)\) 为达到最小值的最小根。先序遍历首先输出根，所以同代价时较小根必然更优；根相同后依次采用左、右子树的最小先序。这个归纳证明最小根选择得到全局字典序最小方案，零频次也不例外。
Knuth 优化¶
非负区间和满足包含单调性与四边形等式。最优搜索树的根单调性给出
因此只需枚举这两个根之间的候选。这个经典结论来自 Knuth, Optimum binary search trees (1971)，这里应用于失败检索频次全为零的情况。
最小根的平局规则可以一致使用。其依据是递推代价满足四边形不等式：扩展右端点不会使一个更小的根从严格劣于已选根变为更优或平局最优；左右对称地，删去左端点也不会迫使根左移。若所有频次为零，得到 \(R(l,r)=l\) ，也满足上述界限。实现从左到右枚举，仅在严格变小时更新根，不使用右端优先的平局规则。
对固定区间长度求和，枚举区间宽度由相邻根之差组成，首尾相消，总候选数为 \(O(n)\) ；共有 \(n\) 种长度，时间为 \(O(n^2)\) .状态、根与前缀和共占 \(O(n^2)\) 空间。完整枚举法时间 \(O(n^3)\) 、空间 \(O(n^2)\) .
重建与实现¶
先输出 \(D(1,n)\) .栈保存待访问区间，每次输出其根，再把右区间、左区间按此顺序压栈，弹出顺序便是根、左、右。空区间跳过。用显式栈可处理零权值导致的链状最优树。
\(D\) 与前缀和用 64 位整数。任一树的代价不超过 \(n^2\max_i f_i\le2.5\times10^{14}\) ，远小于有符号 64 位上界。根表使用整数编号。不得把按整数定义的字典序替换为字符串排序。
数据生成与验证¶
使用 Python 3 标准库运行 tests/generate.py --out-dir <目录> 可按 plan.json 生成输入；可重复使用 --case 选择编号，使用 --std <可执行程序路径> 同时生成输出。先自行以 C++17 编译所需源码。固定计划与种子可重现输入；生成大数据放在题目目录之外。
性能记录保留每份正式输入和源码的哈希、五轮时间及峰值工作集。所有交付方案均通过完整数据。226 个小输入枚举所有搜索树形，独立比较加权深度和整数先序；全部正式输入与完整枚举根程序核对。