首页 > 代码库 > SDUT 2766 小明传奇2
SDUT 2766 小明传奇2
小明传奇2
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
小明不但创建了自己的商店而且选择了建立了自己的货币系统。
传统地，一个货币系统是由1,5,10,20 或 25,50, 和 100的单位面值组成的。
小明想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。
举例来说, 使用一个货币系统 {1,2,5,10,...}产生 18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。 写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数在0 到2^63-1之间。
输入
多组输入，输入到文件末。
货币系统中货币的种类数目是 V (1<=V<=25)。要构造的数量钱是 N (1<= N<=10,000)。
第一行: 二个整数，V 和 N 。
第二行： 可用的货币的面值 。
输出
单独的一行包含那个可能的用这v种硬币凑足n单位货币的方案数。
示例输入
3 101 2 5
示例输出
10
提示
#include <stdio.h>#include <string.h>long long dp[10002];int a[30];int main(){ int i, j; int v, n; while(scanf("%d %d", &v, &n )!=EOF ) { memset(dp, 0, sizeof(dp)); for(i=0; i<v; i++) { scanf("%d", &a[i] ); } dp[0]=1; for(i=0; i<v; i++) { for(j=a[i]; j<=n; j++) { dp[j]=dp[j]+dp[ j-a[i] ] ; } } printf("%lld\n", dp[n] ) ; } return 0;}
SDUT 2766 小明传奇2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。