# 圣辇船直营菓子工房的补货：补充解法

出题人解法：以非递减价格枚举采购方案。Codex（GPT-6）整理递归、模运算和输出。首选方案见[五边形数递推](solution.zh.md)。

先把空方案的余款计入答案。搜索状态的参数为当前最低价格和剩余钱数：可以跳过当前价格，或者买一件当前商品。后一分支购买后，把当前方案的余款计入答案，然后允许继续购买同一价格。只在能产生正余款方案时展开分支；余款为零的方案贡献为零，可省略。

每个非空方案都有唯一的非递减价格序列。跳过价格和购买当前价格的选择唯一确定该序列，因此不会重复；任意正余款方案都能按该序列走到对应节点，所以没有漏计正贡献。空方案另加，零贡献可省略，故总和正确。预算为零时不进入递归。

记 $K=\sum_{s=0}^{X}P_s$ 为不超过预算的拆分总数。非递减方案的购买前缀仍是一种这样的方案，跳过价格的链长至多 $X$ ，故保守时间上界为 $O((X+1)K)$ ，递归空间 $O(X+1)$ .其运行时间随方案数增长，适合小规模理解与独立核对；虽然公式对完整范围正确，是否在参考时限内完成以[性能记录](../../../docs/benchmark-R20.json)为准。它不作为低多项式算法的替代推荐。

程序：[alternative-search.cpp](alternative-search.cpp)。

参考环境中，最大用例的五轮中位时间约为 0.410 秒，低于 0.5 秒参考时限，但仅约 1.22 倍余量，未达到建议的两倍通过余量。因此将其作为备用枚举与核对程序；部署时不承诺它通过完整范围，应优先使用五边形数或背包方案。