蓝桥杯2017年第八届真题-包子凑数 （Java代码）

解题思路:
             背包问题，然后需要求最大公约数。

             很容易可以理解，当所有笼包子全部为偶数，比如2，4，6，那完了，有无限多种方案。

             再看一个例子，当全部为3，6，9的时候，能够推出来嘛？也不能，为什么呢？

             好吧，这就要涉及到求最大公约数的问题，第一个例子，公约数为2，第二个公约数为3.

这里直接给出一个结论，当公约数不为1的时候，他们不能组合出来的数，有无限多个，于是用辗转相除法算一下最大公约数即可。

最难理解的是背包，到底状态方程怎么写？

dp[i][j]的意思，前面i个笼子，能不能组合出j，如果能组合出来，dp[i][j]==1,不能组合出来dp[i][j]==0

if(dp[j-arr[i]]==1)dp[j]=1;   这一段是我觉得最难理解的地方，但是想通了就觉得还挺简单的

先来说说，j-arr[i]是什么意思呢？arr[i]里面，存放的是i笼包子存放的包子个数，j-arr[i]就为少一笼包子个数

那么dp[j-arr[i]]又是啥意思，少一笼包子的个数，能不能被组合出来的状态。

我们来看样例，2笼包子，一笼4个，一笼5个。这是我说了，我要吃8个包子，按照这个思路，我们怎么求解？

我是一个懒人，我不想算，那么我就问老板，你可以给我吃4个包子或者3个包子吗？老板说，嗯，我这里一笼有4个，可以给你啊。

4个包子，可以被组合出来，那么8个包子呢，在基础上多加一笼4个包子的 ，不就组合出来了吗。

如果还不理解，我们再看，当我要很多很多包子，但是我还是不想算？这时候，就需要问很多人了

比如20个包子，你问，老板，可以给我16个包子或者15个包子吗？

老板说可以，但是老板也不想算，这时候，他就只好去问他老婆，老婆，可以给我12个包子或者11个包子吗

同时，他又去问他的员工，小明，你可以给我11个包子或者10个包子吗?

我的天哪，他的员工会怎么做，你想一想？依次类推？

那什么人，是可以自己回答的，同时也不需要思考的呢？被问到4笼包子和5笼包子的人，不信你问问我，我直接给你一笼就好了。

注意事项:

参考代码:

       import java.util.Scanner;

public class Main {

		public static void main(String[] args) {
			Scanner in=new Scanner(System.in);
			int n=in.nextInt();//n笼包子
			int arr[]=new int[105];//arr用来存放第i笼包子能容纳的个数
			arr[1]=in.nextInt();//暂时定最大公约数为temp
			int temp=arr[1];
			for(int i=2;i<=n;i++){
				arr[i]=in.nextInt();
				temp=gcd(temp,arr[i]);//最大公约数又temp和下一笼包子的最大公约数
			}
			
			int dp[]=new int[100005];
			dp[0]=1;
			for(int i=1;i<=n;i++){
				for(int j=arr[i];j<100005;j++){
					if(dp[j-arr[i]]==1)dp[j]=1;//如果dp[j-4]或者dp[j-5]都能够表达，那么在基础上，我多放一笼包子就可以了
				}
			}
			int ans=0;
			for(int i=1;i<100005;i++){
				if(dp[i]!=1)ans++;
			}
			if(temp>1)System.out.println("INF");
			else System.out.println(ans);
	}

		private static int gcd(int a, int b) {
			// TODO Auto-generated method stub
			return  b==0?a:gcd(b,a%b);
		}

}