题目大意:
US 的硬币工分为以下五种:penny: 1c, nickel: 5c, dime: 10c, quarter: 25c, half-dollar: 50c,若Mel去商店里买东西,店家找他 N cents,问使用上面5种penny,共有几种找法?即有几种方法能够凑出N cents?
其中0 <= N <= 30000;
解题思路:
完全背包问题,解决方法就是将N从 1 到 30000 中,每个N有几种凑成方法都算一遍。
状态转移方程: dp[j] += dp[ j - coin[i] ]; 即如果j - coin[i] 能够由coin[i]凑成的话,那么 j 也能由coin[i]凑成,凑成的方法总数就为当前的总量加上 j - coin[i] 的总量。注意,dp的类型要为long long 类型,int的类型不够,会溢出的。(我刚开始没注意,一直错。。。囧!)
代码:
#include <iostream> #include <cstring> #include <string> #include <algorithm> #include <vector> using namespace std; long long dp[30010]={0}; int coin[5] = {1,5,10,25,50}; int main() { long long sum; dp[0] = 1; for( int i = 0; i < 5; i++ ) { for( int j = coin[i]; j <= 30000; j++ ) { if( dp[ j - coin[i] ] ) dp[j] += dp[ j - coin[i] ]; } } freopen( "test.txt", "r", stdin ); freopen( "test.out", "w", stdout ); while( cin>>sum ) { if( dp[sum] == 1 ) { cout<<"There is only 1 way to produce "<<sum<<" cents change."<<endl; continue; } cout<<"There are "<<dp[sum]<<" ways to produce "<<sum<<" cents change."<<endl; } return 0; }
相关推荐
UVA 10474
uva357的栈实现版本
Uva 100 ,问题是The 3n+1 probelm ,可以ac的代码
UVA109的题解,经测试完全正确,还附有题解。
uva272
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva最全ac代码
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
uva 102 357 484 702709 714 825 10128解法与代码,一些自己做的题目,贡献出来
uva10755 ac 代码,可以随意更改下载
UVA 题目,不是很难,试试吧
《算法竞赛入门经典》UVa配套题目pdf版完整
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
uva_trilearn2002 源代码
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
PDF试题
主要是uvaoj习题相关题目 练习题目