学习目标
前置知识与环境
先阅读 第 12 章对应小节，并确保本机可使用 C++17。首次运行可执行 make doctor；Windows 未安装 Make 时可在仓库根使用 pnpm 命令。
题目
按题目给定的分段递归定义计算函数 w(a,b,c)。输入包含多组三元组，以 -1 -1 -1 结束；终止行不输出。
输入格式
每行三个 64 位整数 a b c。当且仅当三者均为 -1 时结束。
输出格式
对每组数据输出 w(a, b, c) = answer，其中空格与标点必须与样例一致。
数据范围
测试组数不超过 10^5；输入可超出 0..20，但有效缓存状态只有 21³ 个。
样例输入
text
1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1样例输出
text
w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1递归契约卡
| 问题 | 本题答案 |
|---|---|
| 子问题契约 | solve(a,b,c) 返回递归定义中的 w(a,b,c)；先处理非正数和大于 20 的边界，再查询或写入缓存。 |
| Divide | 每个非边界状态依题目条件拆成 3 个或 4 个更小参数状态。 |
| Conquer | 对规模严格更小的子问题递归求解；达到最小规模时直接返回。 |
| Combine | 按递归式执行加减；相同状态只求一次。 |
| 终止性检查 | 每次递归都缩短区间、减小规模或把下标映射到更短的一层。 |
WARN易错点
不要先用输入下标访问缓存；负数和大于 20 的参数会越界。
复杂度目标
时间 O(21³ + T)，空间 O(21³)，其中 T 为输入组数。
测试设计提示
公开测试共 20 组、每组 5 分，总分 100 分。它们覆盖样例、最小规模、边界值、重复值、负数或极值、典型回归输入和适度压力数据。测试只读取标准输出；调试信息请写到标准错误。
运行与评分
powershell
cd labs/chapter-12/exercise/E-12-01-function-memoization
make run
# 没有 Make 时，在仓库根执行
pnpm lab:run -- labs/chapter-12/exercise/E-12-01-function-memoization
# 作者与 CI 的严格检查
pnpm lab:verify -- labs/chapter-12/exercise/E-12-01-function-memoization完成清单
思考与复盘
- 如果把子问题契约改成另一种区间语义，边界和合并会怎样变化？
- 哪个最小反例最容易暴露「不要先用输入下标访问缓存；负数和大于 20 的参数会越界。」？
- 递归调用栈保存了哪些信息？能否安全改写成迭代？
题目来源与课程化说明
核心问题参考 洛谷 P1464。本 Lab 为统一的标准输入/输出环境重新表述题面，并独立编写参考实现与测试数据；不复制第三方题解、代码或隐藏测试。若本地输出合同与原平台不同，以上“输出格式”和“递归契约卡”是本 Lab 的判定依据。