博客
关于我
蓝桥杯包子凑数(贝祖定理-动态规划)
阅读量:365 次
发布时间:2019-03-04

本文共 1858 字,大约阅读时间需要 6 分钟。

1. 问题描述:

小明几乎每天早晨都会在一家包子铺吃早餐。这家包子铺有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。

样例输入

2

4
5

样例输出

6

来源:

2. 思路分析:

① 一开始的时候没有什么思路,于是在网上查找了一下解题思路发现这道题目考查的是扩展欧几里得算法相关的知识点,其中使用到了贝祖定理,贝祖定理的描述为:如果a、b是整数,那么一定存在整数x、y使得ax+by=gcd(a,b)。换句话说,如果ax+by=m有解,那么m一定是gcd(a,b)的若干倍。(可以来判断一个这样的式子有没有解)其中一个比较常用的是如果ax+by=1有解,那么gcd(a,b)=1;下面是我对于网上思路的理解。

② 如果题目中给出的每笼包子数目的最大公约数不等于1那么就就会导致无限多个不是gcd(A1,A2,A3...An)倍数的数t使得A1x1 + A2y1 +.... = t 是不存在x1,y1,z1....使得方程具有整数解的这个时候凑不出的包子的数目是存在无限多个的,所以只有当gcd(A1,A2,A3...An) = 1的时候那么m是1的m倍肯定是存在整数解的,所以我们首先需要求解的是所有包子数目的最大公约数如果发现不是1那么肯定存在无限个凑不出的数目的包子直接输出INF即可,如果最大公约数为1那么说明A1x1 + A2y1 +.... = m是整数解的因为这个时候m是1的m倍,当有解的时候就相当于是我有若干个不同重量物品,并且当前最大的背包容量是固定的(这个感觉是由于题目的数据量决定的),通过放置这些物品求解出哪些容量通过这些物品凑不出来的,我们其实可以声明一个长度为10005的列表(根据数据规模大概确定在这个范围吧)通过两层循环来在最大背包容量的情况下放置无限多个物品,如果当前容量能够放置物品那么将这个位置的dp列表值置为1,最终计算出列表中置为1的数目那么就是不能够凑出的包子的数目。

3. 代码如下:

# 计算a与b的最大公约数def gcd(a: int, b: int):    return a if b == 0 else gcd(b, a % b)if __name__ == '__main__':    N = int(input())    baozi = list()    for i in range(N):        baozi.append(int(input()))    g = baozi[0]    for i in range(1, N):        g = gcd(g, baozi[i])    if g != 1:        print("INF")    else:        dp = [0] * 100005        # 第一个数字为1        dp[0] = 1        for i in range(N):            j = 0            while j + baozi[i] < 100001:                # 只有当前位置的值存在的时候通过放置当前的包子那么对应容量的位置置为1                if dp[j]:                    dp[j + baozi[i]] = 1                j += 1        res = 0        for i in range(1, 100001):            if dp[i] == 0:                res += 1        print(res)

 

转载地址:http://dbwg.baihongyu.com/

你可能感兴趣的文章
MySQL 中的外键检查设置:SET FOREIGN_KEY_CHECKS = 1
查看>>
Mysql 中的日期时间字符串查询
查看>>
mysql 中索引的问题
查看>>
MySQL 中锁的面试题总结
查看>>
MySQL 中随机抽样:order by rand limit 的替代方案
查看>>
MySQL 为什么需要两阶段提交?
查看>>
mysql 为某个字段的值加前缀、去掉前缀
查看>>
mysql 主从
查看>>
mysql 主从 lock_mysql 主从同步权限mysql 行锁的实现
查看>>
mysql 主从互备份_mysql互为主从实战设置详解及自动化备份(Centos7.2)
查看>>
mysql 主从关系切换
查看>>
MYSQL 主从同步文档的大坑
查看>>
mysql 主键重复则覆盖_数据库主键不能重复
查看>>
Mysql 事务知识点与优化建议
查看>>
Mysql 优化 or
查看>>
mysql 优化器 key_mysql – 选择*和查询优化器
查看>>
MySQL 优化:Explain 执行计划详解
查看>>
Mysql 会导致锁表的语法
查看>>
mysql 使用sql文件恢复数据库
查看>>
mysql 修改默认字符集为utf8
查看>>