蓝桥杯真题训练 包子凑数（数论）

题解

找到所有数的最大公约数，如果这个数大于1，则说明一定会有数是凑不出来的，即INF，否则的话，用dp去寻找每个数是否能被凑出来，若j-a[i]可以被凑出来，则j一定可以被凑出来，状态转移。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
ll n;
ll a[105];
ll ans;
ll g;
ll dp[1000005];//因为n是1e2 所以这里可以开1e6
int flag=1;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
    g=a[1];
	for(int i=2;i<=n;i++)
	{
		g=__gcd(g,a[i]);//寻找所有数的最大公约数
		
	}
    if(g>1)//如果大于1了 肯定有无数个数找不到
		{
			flag=0;
			
		}
	dp[0]=1;
	if(flag)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=a[i];j<=1000000;j++)
			{
				dp[j]=max(dp[j],dp[j-a[i]]);//j可以由j-a[i]转移过来
			}
		}
		for(int i=1;i<=1000000;i++)
		{
			if(dp[i]==0)
			{
				ans++;
			}
		}
		cout<<ans<<endl;
	}
	else
	{
		cout<<"INF"<<endl;
	}
	return 0;
}