巧用数论与动态规划破解包子凑数问题
本文针对“包子凑数”问题，深入解析如何通过最大公约数（GCD）判断无法组成的数目是否无限，并结合动态规划高效求解有限情况下的具体数目。通过清晰的算法思路、代码实现及示例详解，揭秘数论与动态规划在组合问题中的巧妙应用，帮助读者掌握核心解题技巧。文章还包含复杂度分析与关键注意事项，适合算法学习者和编程爱好者阅读。
题目描述
小明想知道包子铺用给定的蒸笼规格能凑出多少种无法组成的包子数目。若无法组成的数目无限，输出 INF。
输入格式
- 第一行为整数 N N N（蒸笼种数）
- 接下来 N N N 行每行一个整数 A i A_i Ai（每种蒸笼的包子数）
输出格式
- 无法凑出的数目个数，若无限则输出
INF
问题分析
关键条件
若所有 A i A_i Ai 的最大公约数（GCD）不为 1，则无法组成的数目无限。例如，当所有数均为偶数时，无法组成任何奇数。
动态规划思路
当 GCD 为 1 时，使用动态规划判断每个数是否能被组成：
- 定义
dp[i]表示能否凑出i个包子。 - 状态转移：若存在某个 A j A_j Aj 使得
dp[i - A_j]为真，则dp[i]为真。
解题步骤
- 计算 GCD：若 GCD ≠ 1，直接输出
INF。 - 动态规划求解：遍历 1 到 100000，统计无法组成的数目。
代码实现
#include<iostream>
#include<algorithm>
using namespace std;int N;
int num[110];
bool dp[100010]; // dp[i]表示能否组成i个包子// 计算最大公约数
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}int main() {cin >> N;int g = 0; // 初始GCD为0for (int i = 1; i <= N; ++i) {cin >> num[i];g = gcd(g, num[i]); // 更新GCD}// 若所有数的GCD不为1，输出INFif (g != 1) {cout << "INF" << endl;return 0;}dp[0] = true; // 0个包子可以凑出// 动态规划填充数组for (int i = 1; i <= 100000; ++i) {for (int j = 1; j <= N; ++j) {if (i >= num[j] && dp[i - num[j]]) {dp[i] = true; // 标记当前数目可凑}}}// 统计无法凑出的数目int res = 0;for (int i = 1; i <= 100000; ++i) {if (!dp[i]) ++res;}cout << res << endl;return 0;
}
复杂度分析
- 时间复杂度： O ( N × M ) O(N \times M) O(N×M)，其中 M = 1 0 5 M=10^5 M=105 为遍历的最大数， N N N 为蒸笼种数。
- 空间复杂度： O ( M ) O(M) O(M)，存储动态规划状态。
示例解释
样例输入1
2
4
5
输出：6
解释：无法凑出的数为 1, 2, 3, 6, 7, 11。
样例输入2
2
4
6
输出：INF
解释：所有奇数无法凑出，数目无限。
总结
本题结合数论（GCD判断）与动态规划，需注意：
- 先通过 GCD 判断是否为无限情况。
- 动态规划时需覆盖足够大的范围以确保正确性。