洛谷 P1474 货币系统 Money Systems 题解
2024-10-18 03:01:17
P1474 货币系统 Money Systems
题目描述
母牛们不但创建了它们自己的政府而且选择了建立了自己的货币系统。由于它们特殊的思考方式,它们对货币的数值感到好奇。
传统地,一个货币系统是由1,5,10,20 或 25,50, 和 100的单位面值组成的。
母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。
举例来说, 使用一个货币系统 {1,2,5,10,...}产生 18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。 写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数将会适合long long (C/C++) 和 Int64 (Free Pascal),即在0 到2^63-1之间。
输入格式
货币系统中货币的种类数目是 V (1<=V<=25)。要构造的数量钱是 N (1<= N<=10,000)。
第一行: 二个整数,V 和 N 。
第二行: 可用的货币的面值 。
输出格式:
输出格式
单独的一行包含那个可能的用这v种硬币凑足n单位货币的方案数。
输入输出样例
输入 #1
3 10
1 2 5
输出 #1
10
说明/提示
翻译来自NOCOW
USACO 2.3
【思路】
完全背包
很水的一道完全背包题目
【题目大意】
一些面额的货币
组合成n价值一共有多少种组合方式
【核心思路】
假如你有a,b,c面值的硬币
你需要凑足acioi的面额
那么单纯看acioi来说
acioi的组合数量是不是就是
(acioi - a) , (acioi - b) 和 (acioi - c)这三种面额组成方式的和?
所以这就可以跑完全背包了
只不过这里是加起来
不是求最值了
【完整代码】
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int Max = 10005;
int b[Max] = {1},a[30];//默认b[0]为1,也就是在代码中减去一种硬币的面额之后等于0,是这一种硬币一个就可以组成的,所以次数是1
signed main()
{
int v,n;
cin >> v >> n;
for(register int i = 1;i <= v;++ i)
cin >> a[i];
for(register int i = 1;i <= v;++ i)
for(register int j = a[i];j <= n;++ j)
b[j] += b[j - a[i]];
cout << b[n] << endl;
return 0;
}
最新文章
- linux 系统、命令、软件
- mac下彻底卸载mysql方法
- PHP: 手把手编写自己的 MVC 框架实例教程
- Mac OS 电脑播放 iPhone音乐
- [IIS]IIS扫盲(五)
- UICollectionView [NSIndexPath section]: message sent to deallocated instance
- Phantom omini设备开发流程
- post提交/文件上传服务器修改
- 用jQuery绑定事件到动态创建的元素上
- TypeScript 上手教程
- tomcat 配置本地路径映射
- Linux中环境变量中文件执行顺序
- C++对象的内存分布和虚函数表
- 【CSS】定义元素的位置
- window.parent 与 Window.top
- 移动端H5调用摄像头(选择上传图片)
- linux 常用命令,开发记住这些基本能够玩转linux
- 使用Facebook开源代码FBShimmering封装进度显示的ShimmeCircleView
- 51nod 1102 面积最大的矩形
- jsp页面中获取session中的值
热门文章
- 【转载】sqlserver中小数类型float和deciaml类型比较
- Java 之 Session 包含验证码登录案例
- 彻底解决unable to find valid certification path to requested target
- Node.js 实现 MySQL 数据库增删改查
- 复盘一篇讲sklearn库学习文章(上)
- 小米8seroot后更改hosts文件记录
- docker 安装 oracle
- HTML&;CSS基础-html常用的标签
- MSSQL-反弹注入
- C++学习(1)—— 初识C++