標題：包子湊數

小明幾乎每天早晨都會在一家包子鋪吃早餐。他發現這家包子鋪有N種蒸籠，其中第i種蒸籠恰好能放Ai個包子。每種蒸籠都有非常多籠，可以認為是無限籠。

每當有顧客想買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，否則按無效代碼處理。
提交程序時，注意選擇所期望的語言類型和編譯器類型。

package com.tjrac_java_2;import java.util.Scanner;public class TT {static int[] a = new int[100001];static int[] dp = new int[100001];static int n;static int sum = 0;static Scanner sc = null;public static void main(String[] args) {sc = new Scanner(System.in);int n = sc.nextInt();int mark = 1;for (int i = 0; i < n; i++) {a[i] = sc.nextInt();if (i > 0 && mark==1 ) {if (gcd(a[i - 1], a[i]) == 1) {mark = 0;}}}if (mark == 1) {System.out.println("INF");} else {int ans = 0;dp[0]=1;for (int j = 0; j < n; j++) {for (int i = 1; i <= 100000; i++) {if(i-a[j]<0){continue;}if (dp[i - a[j]] == 1) {dp[i]=1;}}}for (int i = 0; i < 100000; i++) {if(dp[i]==0){ans++;}}System.out.println(ans);}}private static int gcd(int i, int j) {return j==0?i:gcd(j,i%j);} }

總結

以上是生活随笔為你收集整理的包子凑数（蓝桥杯）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。