历届试题 包子凑数

完全背包问题，先判所有数的Gcd是否为1，如果不是1的话，显然他们能凑出的数一定是Gcd的倍数，所以一定有无穷个凑不出来，然后两个for解决。

Code：

#include <bits/stdc++.h>
using namespace std;
int dp[10005];
int a[105];
int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a%b);
}
int main()
{
	int n, f = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
		if (i == 0)
			f = a[i];
		else
			f = gcd(f, a[i]);
	}
	if (f != 1)
	{
		puts("INF");
		return 0;
	}
	dp[0] = 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = a[i]; j < 10005; j++)
			dp[j] = max(dp[j], dp[j - a[i]]);
	}
	int cnt = 0;
	for (int i = 1; i < 10005; i++)
		if (!dp[i])
			cnt++;
	printf("%d", cnt);
}