分析
上界:10000/100000
100*100最多上界:10000
模板:完全背包
完全背包:物品可以任意使用多次
0-1背包:物品只可以使用1次
最大公约数
最大公约数为1可以凑出很多个数
最大公约数不为1无法凑出很多个数
状态表示
本题的状态表示是用boolean检查集合是否非空
ACcode
import java.util.*;
public class Main{
static int N=10000;
static boolean f[][]=new boolean [110][N];
public static int gcd(int a,int b){
int c;
while(b!=0){
c=a%b;
a=b;
b=c;
}
return a;
}
public static void main(String []args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int []w= new int [n+10];
int d=0;
for(int i=1;i<=n;i++){
int v=sc.nextInt();
d=gcd(d,v);
w[i]=v;
}
if(d!=1)System.out.println("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>=w[i])f[i][j]|=f[i][j-w[i]];
}
}
int res=0;
for(int k=0;k<N;k++) {
if(!f[n][k])res++;
}
System.out.println(res);
}
}
}