蓝桥杯 - [2013年第四届真题]买不到的数目(数论|动态规划)
发布日期:2021-07-01 00:18:24
浏览次数:3
分类:技术文章
本文共 892 字,大约阅读时间需要 2 分钟。
题目链接:
时间限制:1.0s 内存限制:256.0MB问题描述
小明开了一家糖果店。他别出心裁:把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候,他就用这两种包装来组合。当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。 你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。 本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。输入格式
两个正整数,表示每种包装中糖的颗数(都不多于1000)
输出格式
一个正整数,表示最大不能买到的糖数
样例输入
4 7
3 5
样例输出
17
7
解题思路
可以用完全背包做,也可以利用数论里面的一个公式——两个数最大不能组合的数为两个数之积减去两个数之和。
动态规划:
#include#include int a[2], dp[1000005];int main() { int a[2], ans = 0; scanf("%d%d", &a[0], &a[1]); int n = a[0] * a[1]; dp[a[0]] = dp[a[1]] = 1; for (int i = 0; i < 2; i++) for (int j = a[i]; j <= n; j++) dp[j] += dp[j - a[i]]; for (int i = n; !ans && i; i--) if (!dp[i]) ans = i; printf("%d\n", ans); return 0;}
数论:
#include#include int main() { int a, b; scanf("%d%d", &a, &b); printf("%d\n", a *b - a - b); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/90318481 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月20日 03时54分18秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
MySQL进阶查询(SELECT 语句高级用法)
2019-04-30
Mysql 之主从复制
2019-04-30
【NLP学习笔记】中文分词(Word Segmentation,WS)
2019-04-30
对于时间复杂度的通俗理解
2019-04-30
如何输入多组数据并输出每组数据的和?
2019-04-30
行阶梯型矩阵
2019-04-30
MATLAB指定路径保存图片方法
2019-04-30
JAVA学习笔记6 - 数组
2019-04-30
JAVA学习笔记10 - 继承
2019-04-30
【学习笔记】Android Activity
2019-04-30
location区段
2019-04-30
nginx访问控制、基于用户认证、https配置
2019-04-30
linux内存的寻址方式
2019-04-30
how2heap-double free
2019-04-30
how2heap-fastbin_dup_consolidate
2019-04-30
tf keras SimpleRNN源码解析
2019-04-30
MyBatisPlus简单入门(SpringBoot)
2019-04-30
攻防世界web进阶区web2详解
2019-04-30
xss-labs详解(上)1-10
2019-04-30