历届试题 包子凑数
完全背包问题，先判所有数的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);
}
哔哩哔哩公司氛围 723人发布