货币系统

各位看官老爷们给点赞和评论吧~~Orz

Description

母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。
[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)。

Input

货币系统中货币的种类数目是 V 。 (1<= V<=25)
要构造的数量钱是 N 。 (1<= N<=10,000)
第 1 行: 二整数， V 和 N
第 2 …V+1行： 可用的货币 V 个整数　(每行一个　每行没有其它的数)。

Output

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

Sample Input

3 10
1 2 5

Sample Output

10

Hink

Time Limit:10000MS
Memory Limit:65536K

解题思路

这道题也是动态规划中的完全背包，不过它记下来的不是结果，而是方案数。
状态转移方程： f [ j ] + = f [ j − a [ i ] ] ; f[j]+=f[j-a[i]]; f[j]+=f[j−a[i]];

#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
long long a[10010],m,n,f[10010];
int main()
{
   
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	 cin>>a[i];
	for(int i=1;i<=n;i++)
	{
   
		f[0]=1;
	    for(int j=a[i];j<=m;j++)
	     f[j]+=f[j-a[i]];
    }
    cout<<f[m];
	return 0;
}