牛客网 - [中南林业科技大学第十一届程序设计大赛]兑换零钱(背包问题)
发布日期:2021-07-01 00:18:39
浏览次数:3
分类:技术文章
本文共 830 字,大约阅读时间需要 2 分钟。
题目链接:
时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K 64bit IO Format: %lld题目描述
现有N元钱,兑换成小额的零钱,有多少种换法?币值包括1 2 5分,1 2 5角,1 2 5 10 20 50 100元。
(由于结果可能会很大,输出Mod 10^9 + 7的结果)输入描述
第一行输入一个整数T,代表有T组数据
接下来T行,每行输入1个数N,N = 100表示1元钱。(1 <= N <= 100000)输出描述
输出Mod 10^9 + 7的结果
输入
2
5 4
输出
4
3
备注:
5分钱兑换为零钱,有以下4种换法:
1、5个1分 2、1个2分3个1分 3、2个2分1个1分 4、1个5分
解题思路
类似于完全背包,好像是母函数,推出公式就行了。
#includeusing namespace std;const int MOD = 1E9 + 7;int t, n, dp[100005];int m[] = {1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i = 0; i < 13; i++) for (int j = m[i]; j <= n; j++) dp[j] = (dp[j] + dp[j - m[i]]) % MOD; printf("%d\n", dp[n]); } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/90704802 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年05月01日 20时22分27秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
图书商城:订单模块
2019-05-01
开源全能播放器Vitamio的使用
2019-05-01
使用ViewPager加载页面出现空白
2019-05-01
ImageView scaleType
2019-05-01
RecyclerView notifyItem闪屏问题
2019-05-01
JPA案例
2019-05-01
dubbo学习笔记 十二 dubbo-cluster
2019-05-01
dubbo学习笔记 十三 dubbo-filter
2019-05-01
dubbo学习笔记 十一 dubbo-rpc之模块
2019-05-01
motan学习笔记 五 opentracing学习入门
2019-05-01
爬取博客园博客
2019-05-01
什么是Docker?
2019-05-01
一个基于百度云和图灵的人工智能程序
2019-05-01
用两个栈实现队列
2019-05-01
求列表最长子序列
2019-05-01
重建二叉树
2019-05-01
二进制中1的个数
2019-05-01
合并两个排序的链表
2019-05-01
二叉树的镜像
2019-05-01
树的子结构
2019-05-01