P15057

Money Systems 货币系统

难度 5 级 小学 动态规划入门 背包DP 完全背包 加法原理
讨论 统计 13通过 18提交 72.2%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统. [In their own rebellious way],,他们对货币的数值感到好奇.

传统地,一个货币系统是由 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).

输入

货币系统中货币的种类数目是 V . (1<= V<=25) 要构造的数量钱是 N . (1<= N<=10,000)

第 1 行: 二整数, V 和 N

第 2 ..V+1行: 可用的货币 V 个整数 (每行一个 每行没有其它的数).

输出

单独的一行包含那个可能的构造的方案数.

样例

样例 1
输入
3 10
1 2 5
输出
10

来源

USACO

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交