包子凑数蓝桥杯

标题：包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入
----
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)  

输出
----
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。

例如，
输入：
2  
4  
5   

程序应该输出：
6  

再例如，
输入：
2  
4  
6    

程序应该输出：
INF

样例解释：
对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。  
对于样例2，所有奇数都凑不出来，所以有无限多个。  

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms


请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
提交程序时，注意选择所期望的语言类型和编译器类型。

思路：

有一个数学结论，所有数的最大公约数不为1的话，则这些数不能凑成的数有INF个。

存在一个可以被凑成的结点，且此结点的前min-1（min=Math.min（A[i]）,i=1,2,3,4,5,6....N）个结点都可以被凑成，则此结点以后的结点都可以被凑成。

我这个思路不知道哪里出现了问题，官网只给了75分，望请教。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    
    static int N;
    static int A[];
    static int baoZi[];
    
    static int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
    
    static boolean judge(int c,int min){
        int flag=0;
        for(int i=1;i<min;i++){
            if(baoZi[c-min+i]!=1){
                flag=1;
            }
            if(flag==1){
                return false; 
            }
        }
        return true;
    }
    
    static int solve(int min){
        for(int i=0;i<100000;i++){
            if(baoZi[i]==1){
                for(int j=0;j<N;j++){
                    if(i+A[j]<100000){
                        if(baoZi[i+A[j]]!=1){
                            baoZi[i+A[j]]=1;
                            if(judge(i+A[j],min)){    //已经符合条件
                                int res=i+A[j]-min;
                                return res;
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
    
    public static void main(String[] args){
        Scanner reader=new Scanner(System.in);
        N=reader.nextInt();
        A=new int[N];
        baoZi=new int[100000];
        int min=1000;
        for(int i=0;i<N;i++){
            A[i]=reader.nextInt();
            baoZi[A[i]]=1;    //赋初始值
            min=Math.min(min, A[i]);    //取出最小值
        }
        Arrays.sort(A, 0, N-1);
        int g=A[0];
        for(int i=1;i<N;i++){
            g=gcd(g,A[i]);
        }
        if(g!=1){
            System.out.println("INF");
        }else{
            int count=0;
            int res=solve(min);
            for(int i=1;i<=res;i++){
                if(baoZi[i]!=1){
                    count++;
                }
            }
            System.out.print(count);
        }
    }
}

然后用了一个网上比较简单的方法，其实也是暴力法枚举，但是得了100分。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    
    static int N;
    static int A[];
    static int baoZi[];
    
    static int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
    
    public static void main(String[] args){
        Scanner reader=new Scanner(System.in);
        N=reader.nextInt();
        A=new int[N];
        for(int i=0;i<N;i++){
            A[i]=reader.nextInt();
        }
        baoZi=new int[10001];
        int g=A[0];
        for(int i=1;i<N;i++){
            g=gcd(g,A[i]);
        }
        if(g!=1){
            System.out.print("INF");
        }else{
            baoZi[0]=1;
            for(int i=0;i<N;i++){
                for(int j=0;j+A[i]<baoZi.length;j++){
                    if(baoZi[j]==1){
                        baoZi[j+A[i]]=1;
                    }
                }
            }
            int count=0;
            for(int i=baoZi.length-1;i>=0;i--){
                if(baoZi[i]==0){
                    count++;
                }
            }
            System.out.print(count);
        }
    }
}

包子凑数 蓝桥杯

包子凑数蓝桥杯