有n种蒸笼,每种有无限个,且每种可以蒸Ai个包子,问有多少种包子个数是蒸不出来的。如果有无限多个,输出INF。
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)
一个整数代表答案。如果凑不出的数目有无限多个,输出INF。
2
4
5
6
2
4
6
INF
注意:选择100000长度不是必然的,可以选择更长的数字。经实验验证,对于蓝桥杯测评系统,一维dp对多可设置成10^7。
此外,如果有三个数互质,如19,17,5则这组数不能凑出的数中最大的为n,而19,17不能凑出的最大数为m,则m≥n
int n; int[] arr; int[] dp = new int[10010]; //最多可以10^7 void test() { //如果一组数是互质的,那么他们凑不出来的数有有限个,即当n足够大时,n可以被凑出 Scanner cin = new Scanner(System.in); n = cin.nextInt(); arr = new int[n]; for(int i = 0; i < n; i++) arr[i] = cin.nextInt(); Arrays.sort(arr); if(arr[0] == 1) { //如果可以单独蒸1个 System.out.println(0); return; } //判断他们是否互质 int gcd = arr[0]; for(int i = 1; i< arr.length; i++) gcd = Gcd(gcd,arr[i]); if(gcd!=1) { //他们不是互质的 System.out.println("INF"); return; } //有限个数字可以被凑出 for(int i = 0; i < arr.length; i++) { dp[arr[i]] = 1; for(int j = arr[i]; j < dp.length; j++) { if(dp[j-arr[i]] == 1) dp[j] = 1; //转移方程 } } //计数 int cnt = 0; for(int i = 1; i < dp.length; i++) if(dp[i] == 0) cnt++; System.out.println(cnt); } int Gcd(int a, int b) { if(a % b == 0) return b; else return Gcd(b,a%b); }