P3409. 代表团坐车

解题思路

问题本质

本题是计算方法数的 01背包 板子题。

遍历顺序

• 先顺序遍历物品
• 后逆序遍历背包

核心代码

思路展开 把每个团队的人数看成一件只能整取一次的物品，接驳车容量 max_num 就是背包容量，要统计的是恰好装满的方案数，这是计数型 01 背包。dp[i] 表示车上恰好坐 i 人的方案数，初始 dp[0] = 1，表示谁都不上车是一种基础状态。外层遍历每个团队的人数 num；内层从大到小枚举已有人数 pre（从 max_num - num 递减到 0），把 dp[pre] 累加到 dp[pre + num] 上，含义是：所有能凑出 pre 人的方案，再让当前团队整队上车，就都变成了凑出 pre + num 人的方案。内层上界取 max_num - num 是为了保证 pre + num 不超过车容量；逆序遍历是 01 背包计数的关键——保证累加 dp[pre + num] 时用到的 dp[pre] 还没有算入当前团队的贡献，否则同一团队会被重复上车。全部团队处理完后，dp[max_num] 即恰好坐满的方案数。 复杂度分析 设 k 为团队数量，C 为接驳车容量。

• 时间复杂度：O(k × C)。外层 k 个团队，内层每次至多枚举 C+1 个容量值。按题面约束 k 小于 30、C 小于 100，计算量非常小。
• 空间复杂度：O(C)，只用一个长度 C+1 的一维 dp 数组。

边界与注意事项

• dp[0] = 1 是整个计数的根基：没有这个初始方案，所有后续状态都会保持 0。
• 若没有任何团队组合能恰好坐满，dp[max_num] 保持初始值 0，程序输出 0，无需额外特判。
• 题面保证每个团队的人数不超过接驳车容量；即便出现超容量的团队，内层循环的枚举范围为空，该团队会被自动忽略，不影响正确性。
• 输入格式上，第一行是以逗号分隔的各团队人数（代码按逗号切分），第二行是接驳车容量。