AcWing 1226. 包子凑数
原题链接
中等
作者:
Nazarena
,
2021-01-26 14:59:50
,
所有人可见
,
阅读 433
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int a[100],n,flag = 1,sum = 0,res = 0;
int step[10000],d = 0;
cin >> n;
for(int i=0;i<n;i++)
{
cin >> a[i];
d = gcd(d, a[i]);
}
if (d != 1)
{
cout << "INF";
return 0;
}
sort(a, a+n);
step[0] = 1;
for(int i=1;;i++) //step
{
for(int j=0;j<n;j++) //a
{
if(i>=a[j] && step[i-a[j]] == 1)
{
step[i] = 1;
res++;
break;
}
if(j == n-1)
{
step[i] = 0;
sum ++;
res = 0;
}
}
if(res == a[0])
break;
}
cout << sum;
return 0;
}