牛客网 - [中南林业科技大学第十一届程序设计大赛]兑换零钱(背包问题)
发布日期:2021-07-01 00:18:39
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月08日 14时15分02秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
决策树 Decision tree
2019-04-30
MATLAB与CUDA
2019-04-30
Linux png转jpg (convert命令)
2019-04-30
Ubuntu更新后终端中字体的颜色全是白色
2019-04-30
vscode git
2019-04-30
基于MATLAB的二进制数字调制与解调信号的仿真——2PSK
2019-04-30
基于MATLAB的模拟调制信号与解调的仿真——DSB
2019-04-30
HDU - 1166 敌兵布阵 (树状数组模板题/线段树模板题)
2019-04-30
CodeForces - 456C Boredom (dp)
2019-04-30
CodeForces - 675A Infinite Sequence(简单数论 细节)
2019-04-30
CodeForces - 1042B Vitamins (思维)
2019-04-30
ACM 2013 长沙区域赛 Collision (几何)
2019-04-30
ACM 2014 鞍山区域赛 E - Hatsune Miku (dp)
2019-04-30
反向传播&梯度下降 的直观理解程序(numpy)
2019-04-30
CodeForces - 931B World Cup (思维 模拟)
2019-04-30
ACM 2017 北京区域赛 J-Pangu and Stones(区间dp)
2019-04-30
java常用类 String面试题
2019-04-30
利用ffmpeg合并音频和视频
2019-04-30