AcWing 1226. 包子凑数
原题链接
中等
作者:
ML_manong
,
2024-02-19 17:35:17
,
所有人可见
,
阅读 22
//朴素版
// #include <bits/stdc++.h>
// using namespace std;
// const int N = 10000;
// bool f[110][N];
// int n;
// int v[110];
// int gcd(int a, int b)
// {
// return b ? gcd(b, a % b) : a;
// }
// int main()
// {
// cin >> n;
// int d = 0;
// for(int i = 1; i <= n; i ++)
// {
// cin >> v[i];
// d = gcd(d, v[i]);
// }
// if(d != 1) puts("INF");
// else
// {
// f[0][0] = true;
// for(int i = 1; i <= n; i ++)
// for(int j = 0; j < N; j ++)
// {
// f[i][j] |= f[i - 1][j];
// if(j >= v[i]) f[i][j] |= f[i][j - v[i]];
// }
// int res = 0;
// for(int i = 1; i < 10000; i ++)
// if(!f[n][i]) res ++;
// cout << res << endl;
// }
// }
//空间优化版
#include <bits/stdc++.h>
using namespace std;
const int N = 10000;
bool f[N];
int n;
int v[110];
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
cin >> n;
int d = 0;
for(int i = 1; i <= n; i ++)
{
cin >> v[i];
d = gcd(d, v[i]);
}
if(d != 1) puts("INF");
else
{
f[0] = true;
for(int i = 1; i <= n; i ++)
for(int j = v[i]; j < N; j ++)
f[j] |= f[j - v[i]];
int res = 0;
for(int i = 1; i < 10000; i ++)
if(!f[i]) res ++;
cout << res << endl;
}
return 0;
}