蓝桥杯-包子凑数 | 小彦同学的摸鱼空间

type

status

date

slug

summary

📝 题目：包子凑数

对于这道题目，第一眼看过去很长，不好理解但是实际上我们可以先把他转换为一道不定方程ax+by=C

当有n个数则为,A0*X0+A1*X1+A2*X2+A3*X3+An*Xn=C 然后根据这个公式，想一下这个公式的求解条件

我们知道，不定方程ax+by=c中，想要不出现无限解的情况，那么a跟b必须互质这里补充一个公式：也就是a跟b可以凑出来的C最大为a*b-a-b

根据这一段文字我们转换成代码的第一步就是要判断每一笼包子Ai之间是否互质，不互质的话就是无数解，直接输出INF

然后我们直接来循环从0到最大的C，看看能否满足ax+by=C

但是仔细一想，可以发现这其实是个完全背包问题也就是判断N个价值为Ai的物品里是否能选出总价值等于C的物品能选出来就把dp[i]设为true

那么要如何选呢这里的方法就是当每输入一个数时，则循环10000个数，看看dp[i]有没有true,有true则代表这个C是可以被组成的,则把i跟输入的数相加作为dp的下标，设置这个i+a[i]为true

最后循环找出有多少个false即为结果

💡

刚开始写文章不久,许多地方可能有疏漏，欢迎您在底部评论区留言，一起交流~