hdu 1284
2024-08-30 16:50:40
钱币兑换问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7261 Accepted Submission(s): 4265
Problem Description
在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input
每行只有一个正整数N,N小于32768。
Output
对应每个输入,输出兑换方法数。
Sample Input
2934 12553
Sample Output
718831 13137761
Author
SmallBeer(CML)
Source
Recommend
这题可以采用母函数或者递推或者其他规律。
设d[i][j]为前i个硬币可以兑换j的兑法,考虑第i个,要么不取,兑法就为d[i-1][j],要么取,兑法就为d[i-1][j-v[i]];v[i]==i;
d[i][j]就等于这两种情况之和.(每种硬币的取还是不取的选择,从结果来看,能够包含兑换成j的硬币序列组合,就是说决策能够包含了所以可能的结果)。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long d[];
void init()
{
memset(d,,sizeof(d));
}
int main()
{
int n;
while(~scanf("%d",&n))
{
init();
if(n==)
{
printf("0\n");
continue;
}
if(n==)
{
printf("1\n");
continue;
}
d[]=;
for(int i=;i<=;i++)
for(int j=i;j<=n;j++)
{ d[j]=d[j]+d[j-i];
}
printf("%lld\n",d[n]);
}
return ;
}
最新文章
- vim添加未识别文件类型
- 第六课——UIDynamicAnimator
- ansible执行playbook时间显示的python脚本
- DIOCP之注册编码解码器与ClientContext
- hdu 4268 multiset+贪心
- [转载] 新浪微博MySQL优化的小结和反思
- 【BZOJ】【1911】【APIO2010】特别行动队commando
- JSONObject和JSONArray
- Windows移动开发(一)——登堂入室
- xlrd doc
- eclipse自定义new建
- intersect for multiple vectors in R
- 7_SQL Server通过代码删除数据
- MyEclipse的Debug模式启动缓慢
- RESTful API接口文档规范小坑
- Scrapy Selectors 选择器
- IDEA抛出No bean named &#39;cacheManager&#39; available解决方法
- Java-从Double类型精度丢失认识BigDecimal
- rsync简介与rsync+inotify配置实时同步数据
- Oracle随机排序函数和行数字段
热门文章
- HDU 5245
- Vim enhance part1
- Spring注解 @Component、@Repository、@Service、@Controller @Resource、@Autowired、@Qualifier 解析
- 从零开始写STL—哈希表
- 时间戳转换成DateTime
- loj6169 相似序列(可持久化线段树)
- Java异常错误重试方案研究(转)(spring-retry/guava-retryer)
- Excel小tips - 设置指定可选填充内容
- C# Queue与RabbitMQ的爱恨情仇(文末附源码):Q与MQ消息队列简单应用(二)
- mysql手记