题目描述
问题简化:
a0,a1,…,an一组数,凑不出的数有多少个
设gcd(a0,a1,..,an)=d
1.d!=1,则a0x1+a1x2+…+anxn能凑出的数肯定是d的倍数,一切不是d的倍数的数都凑不出来,所以有INF个
2.d==1
我们知道gcd(p,q)=1时,p,q不能凑出的最大数为(p-1)(q-1)-1
所以本题就是看1-N中有多少个数不能凑出,N可以取10000,因为(100-1)*(99-1)-1<10000
核心
然后转化为完全背包问题,n个数,每个数可取无限个,看看能不能凑出某数
状态表示
f[i][j]:
状态:在前i个数中选,总和为j的所有选法
属性:能否实现,bool
状态计算:
第i个数选0,1,2,3...个f[i][j]=f[i-1][j] | f[i-1][j-a[i]] | f[i-1][j-2*a[i]] | ...
f[i][j-a[i]]=f[i-1][j-a[i]]|f[i-1][j-2*a[i]]|...
所以f[i][j]=f[i-1][j]|f[i][j-a[i]]
最后判断一下1-N每个数是否能被凑出,不能凑出就res++
转化为一维:由于j-a[i]<j,用的是第i层的j-a[i],所以第i层先要更新完j-a[i],再更新j,所以j从小到大枚举
二维写法
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int a[110];
int f[110][N];
int n;
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>>a[i];
d=gcd(d,a[i]);
}
if(d!=1) cout<<"INF"<<endl;
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>=a[i]) f[i][j] |= f[i][j-a[i]];
}
}
int res=0;
for(int i=0;i<N;i++)
{
if(!f[n][i]) res++;
}
cout<<res<<endl;
}
return 0;
}
一维写法
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int a[110];
int f[N];
int n;
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>>a[i];
d=gcd(d,a[i]);
}
if(d!=1) cout<<"INF"<<endl;
else
{
f[0]=true;
for(int i=1;i<=n;i++)
{
for(int j=a[i];j<N;j++)
{
f[j] |= f[j-a[i]];
}
}
int res=0;
for(int i=0;i<N;i++)
{
if(!f[i]) res++;
}
cout<<res<<endl;
}
return 0;
}