💻 爱丽丝的人偶素材采购
华为 · 动态规划 · 算法编程题
华为
动态规划
n ≤ 10
时限 1 秒 / 256 MB
题目描述
爱丽丝正在为制作新的人偶准备素材。她需要购买 n 种不同的素材，每种素材的单价分别为 a_1, a_2, ..., a_n 。为了保证每一种人偶都能顺利完成，爱丽丝制定了一个严格的计划：她必须为每种素材至少购买一个。
现在爱丽丝手中恰好有 b 元，她希望知道有多少种不同的采购方案，能够恰好耗尽这 b 元预算。需要注意的是，即使两种素材的单价相同，它们也被视为不同的素材种类。
输入输出
输入描述
输入包含单组测试数据。
第一行包含一个整数 b ( 0 ≤ b ≤ 100 )，代表爱丽丝的总预算。
第二行包含若干个以空格分隔的整数，代表每种素材的单价 a_i ( 1 ≤ n ≤ 10, 1 ≤ a_i ≤ 50 )。
输出描述
输出一个整数，表示恰好耗尽预算的采购方案总数。
注意：答案可能超过 32 位整数的范围，请使用 64 位整数（如 C++ 中的 `long long`）。
样例共 1 组
样例 1 · 在样例中，预算为 10，有两种单价分别为 1 和 2 的素材。
1. 首先，每种素材必须至少买一个，消耗金额为 1 + 2 = 3 元。
2. 剩余预算为 10 - 3 = 7 元。
3. 使用单价为 1 和 2 的素材凑齐 7 元的方案共有 4 种：
- 购买 7 个单价为 1 的素材。
- 购买 5 个单价为 1 的素材和 1 个单价为 2 的素材。
- 购买 3 个单价为 1 的素材和 2 个单价为 2 的素材。
- 购买 1 个单价为 1 的素材和 3 个单价为 2 的素材。
因此输出为 4。
算法解析依据充分
考点：动态规划
数据规模 n ≤ 10 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
题目画像
- 数据规模：n ≤ 10
- 元素值域：b ≤ 100，a_i ≤ 50（注意整数类型选择，避免溢出）
- 复杂度门槛：允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
- 源站时限：1 秒（牛客口径，非本题专属门槛）
解题思路
推荐方向：动态规划
本题切入点
「每种至少买一个、恰好花完 b 元」的方案计数：先扣掉每种一个的基础花费，再用完全背包做方案数 DP，答案可能超 32 位需用 64 位整数。
把问题拆成子问题，用状态表示「已处理到哪儿」，靠转移方程递推。
思路框架（动态规划 通法 · 非本题专属）
- 定义状态：dp[i] / dp[i][j] 表示什么（这是最关键的一步，状态定义错就全错）。
- 写转移方程：当前状态由哪些更小的状态推来。
- 确定初始条件与遍历顺序（保证用到的状态已算好）。
- 确定答案取哪个状态；数值大时全程取模。
实现要点：一般是「先枚举阶段，再枚举状态，最后枚举决策」三层循环；空间大时可滚动数组优化。
复杂度：时间 O(状态数 × 转移代价) ｜ 空间 O(状态数)
该范式的通法易错点
- 状态定义不完整（漏了必要维度），导致子问题之间有后效性。
- 初始化写错（尤其「恰好」与「至多」的初值差别）。
- 遍历顺序与依赖方向不一致。
对照本题
- 数据规模 n ≤ 10，允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
- 元素值域最大到 100 —— 求和 / 相乘时记得开 64 位整数。
样例解读
样例 1：输入 10 / 1 2 → 输出 4
在样例中，预算为 10，有两种单价分别为 1 和 2 的素材。
- 首先，每种素材必须至少买一个，消耗金额为 1 + 2 = 3 元。
- 剩余预算为 10 - 3 = 7 元。
- 使用单价为 1 和 2 的素材凑齐 7 元的方案共有 4 种：
- 购买 7 个单价为 1 的素材。
- 购买 5 个单价为 1 的素材和 1 个单价为 2 的素材。
- 购买 3 个单价为 1 的素材和 2 个单价为 2 的素材。
- 购买 1 个单价为 1 的素材和 3 个单价为 2 的素材。
因此输出为 4。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2026年-华为-04月23号留学生开发岗。
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解