【SSL】货币系统
发布时间
阅读量：
阅读量
货币系统
各位看官老爷们给点赞和评论吧~~Orz
Description
母牛们不仅建立了她们自己的政府而且最终决定创立了属于她们的金融体系。
在她们叛逆的精神指引下（In their rebellious spirit），她们对于货币的价值产生了浓厚的兴趣。
通常情况下，一个货币体系由诸如1、5、10、20等单位面额或由25、50及100等面额构成。
这些母体显然对构建特定金额的方法充满好奇：从简单的组合到复杂的排列方式都令她们着迷。
例如，在拥有硬币集合{1分、2分、5分、1角}的情况下凑出总共十八分钱的方式包括：十八枚一分；九枚两分；八枚两分加两枚一分；三枚五分加一枚两分和一枚一分等等其他组合方式。
设计一个程序能够计算出给定体系下能达到指定金额的所有可能组合数是一个极具挑战性的任务。
确保所求得的结果足够大以适应长整型数据类型的需求（C/C++中的long long或Pascal中的Int64）。
Input
在货币系统中，货币种类的数量为V（其中V在1到25之间）。
所需求解的数量币种为N（其中N在1到1万之间）。
第一行包含两个整数：V和N。
从第二行到第V+1行共包含可用的货币面值信息，每个面值信息占一行且不包含多余内容。
Output
单独的一行包含那个可能的构造的方案数。
末尾有空行
Sample Input
3 10
1 2 5Sample Output
10Hink
Time Limit:10000MS
Memory Limit:65536K
解题思路
此问题同样属于动态规划中的complete knapsack problem，并未记录最终的结果值（result value），而是记录了可行解的数量（number of feasible solutions）。状态更新方程为：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;
}全部评论 (0)
还没有任何评论哟~