2.3.4 Money Systems 货币系统

code

6 年前

时间： 1ms 内存：64M

描述：

母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。
[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 个整数　(每行一个　每行没有其它的数)。

输出：

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

示例输入：

3 10
1 2 5

示例输出：

提示：

参考答案（内存最优[828]）：

#include<stdio.h>
long long n,a[10001],t,i,j,b[26];
int main()
{
	
	while(scanf("%lld%lld",&t,&n)!=EOF)
	{
		for(i=0;i<t;i++)
			scanf("%lld",&b[i]);
		for(i=1;i<=n;i++)
			a[i]=0;
		a[0]=1;
		for(i=0;i<t;i++)
			for(j=b[i];j<=n;j++)
				a[j]=a[j]+a[j-b[i]];
		printf("%lld\n",a[n]);
	}
	return 0;
}

参考答案（时间最优[0]）：

#include<cstdio>
#include<iostream>
using namespace std;
long long int dp[10005];
int n,m;
long long int a[30];
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	 scanf("%d",&a[i]);
	 dp[0]=1;
	 for(int i=1;i<=n;i++)
	  {
	  	for(int j=a[i];j<=m;j++)
	  	{
	  		dp[j]=max(dp[j],dp[j-a[i]]+dp[j]);
		}
	  }
	  printf("%lld",dp[m]);
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。