思路:根据裴蜀定理,当所有种类的蒸笼包子数的最大公约数不为1时,凑不出的包子数为无限多,因为无论蒸笼怎么组合都必须得是gcd得倍数,gcd不为1一定会有凑不出的。如果能够凑的出的有限,那么到达某个界限后都是凑得出的,这个界限为Ai*Ai=10000,或许会有人问为啥是这个数,这个具体证明我也搞不出,但可以模拟一下你取任意两个互质的数,如6,7,会发现42之后任意一个数都是可以通过6,7组合出来,姑且就当个结论记了八。然后就是对凑不出的数的一个求解,这个可以通过完全背包解决。

dp[i] 表示凑出i个包子的方法总数,简单说就是如果其>=1就凑得出,==0就凑不出。

状态转移方程: dp[i]=dp[i-第j种蒸笼包子数]+1 (dp[i-第j种蒸笼包子数]>=1) 当i-第j种蒸笼包子数是可以凑成的,那么我只需对其+第j种蒸笼包子数就可以凑成i个包子数。

Code:

#include<iostream>
#include<map>
#include<algorithm>
#include<cmath>
#include<set>
#include<string>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 1e6 + 5;

ll dp[10005];

int lst[Max];

int gcd(int a, int b)
{
   
	if (a == 0)return b;
	return gcd(b % a, a);
}

int main()
{
   
	int n;cin >> n;
	for (int i = 1;i <= n;i++)cin >> lst[i];

	int g = lst[1];
	for (int i = 2;i <= n;i++) g = gcd(g, lst[i]);

	if (g != 1)cout << "INF" << endl;
	else
	{
   
		dp[0] = 1;
		for (int i = 1;i <= n;i++)
		{
   
			for (int j = 1;j <= 10004;j++)
			{
   
				if (j - lst[i] >= 0 && dp[j - lst[i]] >= 1)dp[j]++;
			}
		}
		int ans = 0;
		for (int i = 1;i <= 10004;i++)
		{
   
			if (dp[i] == 0)ans++;
		}
		cout << ans;
	}
}