REALHW169 爱丽丝的人偶素材采购

解题思路

每种素材至少买一个，先强制每种各买一个，从预算中扣除总花费。剩余预算用完全背包（求方案数）来解决。

转化过程：

1. c -= sum(arr)：扣除每种必买一个的花费
2. 若剩余预算 < 0，无解输出 0
3. 对剩余预算 c，求用这些素材凑出恰好 c 元的方案数（每种素材可无限购买）

完全背包求方案数：dp[j] 表示凑出金额 j 的方案数，转移方程 dp[j] += dp[j - cost]。

代码实现

c = int(input())
arr = list(map(int, input().split()))
c -= sum(arr)
if c < 0:
    print(0)
    exit()

dp = [0] * (c + 1)
dp[0] = 1

for cost in arr:
    for j in range(cost, c + 1):
        dp[j] += dp[j - cost]

print(dp[c])

代码解析

以示例 b=10, arr=[1,2] 为例：

预处理：c = 10 - (1+2) = 7，剩余 7 元自由分配。

DP 过程（外层按素材种类遍历，内层正序遍历金额）：

先处理 cost=1：

dp = [1, 1, 1, 1, 1, 1, 1, 1]
// 凑任意金额只用素材1，方案都是1种

再处理 cost=2：

dp[2] = 1 + dp[0] = 1 + 1 = 2
dp[3] = 1 + dp[1] = 1 + 1 = 2
dp[4] = 1 + dp[2] = 1 + 2 = 3
dp[5] = 1 + dp[3] = 1 + 2 = 3
dp[6] = 1 + dp[4] = 1 + 3 = 4
dp[7] = 1 + dp[5] = 1 + 3 = 4

最终 dp[7] = 4，对应 4 种方案。

为什么内层正序：正序遍历允许同一物品被多次选取（完全背包），逆序则是 0-1 背包（每件最多选一次）。

复杂度分析

• 时间复杂度：O(n × c)，n ≤ 10，c ≤ 100，最多 1000 次运算
• 空间复杂度：O(c)