专栏首页数据结构与算法P1474 货币系统 Money Systems

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

这是一个裸完全背包问题,

虽然题解里写的都是一维的,但完全背包其实可以用二维去写。。

动态转移方程:

dp[i][j]=dp[i-1][j]+dp[i][j-a[i]];(j>=a[i])

dp[i][j]=dp[i-1][j];(j<a[i])

初始化:

dp[i][0]=1

但是二维的不论是在空间还是在代码复杂度上都劣于一维,但略微易懂。

注意开long long !!!!!!!!!!!!!!!!!

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define lli long long int 
 7 using namespace std;
 8 const lli MAXN=10001;
 9 void read(lli &n)
10 {
11     char c='+';lli x=0;bool flag=0;
12     while(c<'0'||c>'9')
13     {c=getchar();if(c=='-')flag=1;}
14     while(c>='0'&&c<='9')
15     {x=x*10+(c-48);c=getchar();}
16     flag==1?n=-x:n=x;
17 }
18 lli dp[31][10001];
19 lli v,n;
20 lli a[30];
21 int main()
22 {
23     read(v);// 拥有的种类
24     read(n);// 需要构造的钱
25     for(lli i=1;i<=v;i++)
26     {
27         read(a[i]);
28         //dp[i][a[i]]=1;
29         dp[i][0]=1;
30     }
31     for(lli i=1;i<=v;i++)
32         for(lli j=1;j<=n;j++)
33             if(j>=a[i])
34                 dp[i][j]=dp[i-1][j]+dp[i][j-a[i]];
35             else 
36                 dp[i][j]=dp[i-1][j];
37     printf("%lld",dp[v][n]);
38     return 0;
39 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ 3450: Tyvj1952 Easy

    Description 某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:( 我们来简化一下这个游戏的规则 有n次点击要做,成功了就是o...

    attack
  • P2051 [AHOI2009]中国象棋

    题目描述 这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大...

    attack
  • P2327 [SCOI2005]扫雷

    题目描述 ? 输入输出格式 输入格式: 第一行为N,第二行有N个数,依次为第二列的格子中的数。(1<= N <= 10000) 输出格式: 一个数,即第一列中...

    attack
  • Leetcode 91. Decode Ways 解码方法(动态规划,字符串处理)

    给一串包含数字的加密报文,求有多少种解码方式 举个例子,已知报文"12",它可以解码为AB(1 2),也可以是L (12) 所以解码方式有2种。

    racaljk
  • 动态规划之博弈问题

    博弈类问题的套路都差不多,下文举例讲解,其核心思路是在二维 dp 的基础上使用元组分别存储两个人的博弈结果。掌握了这个技巧以后,别人再问你什么俩海盗分宝石,俩人...

    五分钟学算法
  • SAP CRM和C4C数据同步的两种方式概述:SAP PI和HCI

    SAP Cloud for Customer(C4C)和SAP其他传统产品进行数据同步的方式,如下图所示,可以使用SAP Netweaver Process I...

    Jerry Wang
  • 【深度分析】汽车零部件供应商管理+采购体系

    汽车行业虽然是制造行业,但是其采购管理有其特有的结构和特点,汽车是大件,其构造复杂,零部件通常有几万个,不同的车型要求跟标准都不一样,加之,汽车总成本有三分之二...

    数商云市场营销总监
  • 作为 Java 开发者,你需要了解的堆外内存知识

    本文来自作者 应书澜 在 GitChat 上分享 「深入解读 Java 堆外内存(直接内存)」

    CSDN技术头条
  • 十分钟学会用Go编写Web中间件

    中间件(通常)是一小段代码,它们接收一个请求,对其进行处理,每个中间件只处理一件事情,完成后将其传递给另一个中间件或最终处理程序,这样就做到了程序的解耦。如果没...

    KevinYan
  • saltstack快速入门

    Salt,一种全新的基础设施管理方式,部署轻松,在几分钟内可运行起来,扩展性好,很容易管理上万台服务器,速度够快,服务器之间秒级通讯

    萧晚歌

扫码关注云+社区

领取腾讯云代金券