🍑 算法题解专栏
🍑 洛谷 P8646 包子凑数
[蓝桥杯 2017 省 AB] 包子凑数
题目描述
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 N N N 种蒸笼,其中第 i i i 种蒸笼恰好能放 A i A_i Ai 个包子。每种蒸笼都有非常多笼,可以认为是无限笼。
每当有顾客想买 X X X 个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有 X X X 个包子。比如一共有 3 3 3 种蒸笼,分别能放 3 3 3 、 4 4 4 和 5 5 5 个包子。当顾客想买 11 11 11 个包子时,大叔就会选 2 2 2 笼 3 3 3 个的再加 1 1 1 笼 5 5 5 个的(也可能选出 1 1 1 笼 3 3 3 个的再加 2 2 2 笼 4 4 4 个的)。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 3 3 种蒸笼,分别能放 4 4 4 、 5 5 5 和 6 6 6 个包子。而顾客想买 7 7 7 个包子时,大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入格式
第一行包含一个整数 N N N。 ( 1 ≤ N ≤ 100 ) (1 \le N \le 100) (1≤N≤100)。
以下 N N N 行每行包含一个整数 A i A_i Ai。 ( 1 ≤ A i ≤ 100 ) (1 \le A_i \le 100) (1≤Ai≤100)。
输出格式
一个整数代表答案。如果凑不出的数目有无限多个,输出 INF
。
样例 #1
样例输入 #1
2
4
5
样例输出 #1
6
样例 #2
样例输入 #2
2
4
6
样例输出 #2
INF
提示
对于样例 1 1 1,凑不出的数目包括: 1 , 2 , 3 , 6 , 7 , 11 1,2,3,6,7,11 1,2,3,6,7,11。
对于样例 2 2 2,所有奇数都凑不出来,所以有无限多个。
蓝桥杯 2017 省赛 A 组 H 题。
🍑 思路
🍁 裴蜀定理:当 gcd(a,b) == 1 时,这两个数最大不能凑出来的数是:(a-1)(b-1)-1
🍁 数据最大取到 100,最大的两个互质数 为 100 和 99,那 最大不能凑出的数 小于 98*99
🍑 完全背包二维版文章来源:https://www.toymoban.com/news/detail-426033.html
import java.util.*;
public class Main
{
static int N = 110, M = 10010;
static int[] a = new int[N];
static boolean[][] f = new boolean[N][M];
static int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int d = 0;// 任何数 和 0 的最大公约数都是 它本身
for (int i = 1; i <= n; i++)
{
a[i] = sc.nextInt();
d = gcd(d, a[i]);
}
if (d != 1)
System.out.println("INF");
else
{
f[0][0] = true;
for (int i = 1; i <= n; i++)
for (int j = 0; j < M; j++)
{
f[i][j] = f[i - 1][j];
if(j >= a[i])
f[i][j] |= f[i][j-a[i]];
}
int res = 0;
for(int i = 0; i < M; i++)
{
if(!f[n][i])
res++;
}
System.out.println(res);
}
}
}
🍑 滚动数组优化版文章来源地址https://www.toymoban.com/news/detail-426033.html
import java.util.Scanner;
public class Main
{
static int N = 110, M = 10010;
static int[] a = new int[N];
static boolean[] f = new boolean[M];
static int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int d = 0;// 任何数 和 0 的最大公约数都是 它本身
for (int i = 1; i <= n; i++)
{
a[i] = sc.nextInt();
d = gcd(d, a[i]);
}
if (d != 1)
System.out.println("INF");
else
{
f[0] = true;
for (int i = 1; i <= n; i++)
for (int j = a[i]; j < M; j++)
{
f[j] |= f[j - a[i]];
}
int res = 0;
for (int i = 0; i < M; i++)
{
if (!f[i])
res++;
}
System.out.println(res);
}
}
}
到了这里,关于蓝桥省赛 包子凑数 完全背包的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!