资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有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。
测试样例1
Input： 2 4 5 Output： 6 Explanation： 凑不出的数目包括：1, 2, 3, 6, 7, 11。测试样例2
Input： 2 4 6 Output： INF Explanation： 所有奇数都凑不出来，所以有无限多个。ACcode：
import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Arrays; public class Main { static final int INF = 0x33333333; public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int)in.nval, val[] = new int[n], lcm = INF; for (int i = 0; i < n; i++) { in.nextToken(); val[i] = (int)in.nval; } Arrays.sort(val); for (int i = 1, bgcd = val[0], blcm = val[i]; i < n; i++) { bgcd = gcd(bgcd, val[i]); blcm = blcm * val[i] / bgcd; if (bgcd == 1) { lcm = blcm; break; } } if (lcm == INF) System.out.print("INF"); else { int cnt = 0, dp[] = new int[lcm]; for (int i = 1; i < lcm; i++) { dp[i] = INF; for (int j = 0; j < n && i - val[j] >= 0; j++) dp[i] = min(dp[i], dp[i - val[j]] + 1); if (dp[i] == INF) cnt++; } System.out.print(cnt); } } static int gcd(int a, int b) { return b == 0? a: gcd(b, a % b); } static int min(int a, int b) { return a < b? a: b; } }和之前做的一道 PREV-8 很像
