2467 - 货币系统
时间限制 : 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)
<table border="1">
<tbody>
<tr>
<td>
<!--mstheme--><span><span>第 1 行:</span><!--mstheme--></span>
</td>
<td>
<!--mstheme--><span><span> 二整数， V 和 N</span><!--mstheme--></span>
</td>
</tr>
<tr>
<td>
<!--mstheme--><span><span>第 2 ..V+1行：</span><!--mstheme--></span>
</td>
<td>
<!--mstheme--><span><span>可用的货币 V
个整数 (每行一个 每行没有其它的数)。
</td>
</tr>
</tbody>
</table>
题目输出
单独的一行包含那个可能的构造的方案数。
输入/输出样例
输入格式
3 10 1 2 5
输出格式
10
C++解答
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; int main() { int v,n; int a[25]; long long d[10001]; while(scanf("%d%d",&v,&n)!=EOF) { for(int i=0;i<v;i++) scanf("%d",&a[i]); sort(a,a+v); memset(d,0,sizeof(d)); d[0]=1; for(int i=0;i<v;i++) for(int j=a[i];j<=n;j++) d[j]+=d[j-a[i]]; printf("%lld\n", d[n]); } return 0; }