蓝桥杯2017年第八届真题-包子凑数 （C++代码）

解题思路:另数组全部为0，能够装出来的设为1（遍历大数组，不停的往后迭代，若b[i-a[j]]不是0，即可赋值，具体如下），最后数数

注意事项:判断公约数 哦
参考代码:

#include <iostream>

using namespace std;

#define N 100000

int a[100]={0},b[N]={0};

int gy(int a,int b)//判断公约数 

{

while(a%b!=0)

{

int c=a%b;

a=b;

b=c;

}

return b;

} 

int main()

{

int n;

cin>>n;

for(int i=0;i<n;i++) cin>>a[i]; 

if(n==1)//判断n=1 

{

if(a[0]!=1) cout<<"INF"<<endl;

else cout<<0<<endl;

return 0;

}

int gys=a[0];

for(int i=1;i<n;i++)

{

gys=gy(gys,a[i]);

}

if(gys!=1)//公约数不为1，直接输出无限 

{

cout<<"INF"<<endl;

return 0;

} 

b[0]=1;

for(int j=0;j<n;j++)//核心代码 

{

for(int i=a[j];i<N;i++)

{

if(b[i-a[j]]) b[i]=1;//不停的往后迭代，若b[i-a[j]]不是0，即可赋值

}

}

int sum=0;

for(int i=1;i<N;i++)//数0 

{

if(b[i]==0)

sum++;

}

cout<<sum<<endl;

return 0;

}