hdu1284 sdut2777 钱币兑换问题(完全背包,递推,母函数)

2024-06-15 16:18

本文主要是介绍hdu1284 sdut2777 钱币兑换问题(完全背包,递推,母函数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

钱币兑换问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4735    Accepted Submission(s): 2675


Problem Description
在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

Input
每行只有一个正整数N,N小于32768。

Output
对应每个输入,输出兑换方法数。

Sample Input
  
2934 12553

Sample Output
  
718831 13137761

 

分析:

就是政治老师讲的怎么忘瓶子里装石沙水的问题,要想装得满,先装石头再装沙子最后灌水!

所以只肖考虑换多少3分钱,再考虑用2毛钱有多少种替换方法,1分的自动填满

 

#include<stdio.h>
int main()
{int i,n,s;while(scanf("%d",&n)!=EOF){s=n/3+1;for(i=0;i<=n/3;i++)s+=(n-i*3)/2;printf("%d\n",s);}return 0;
}


 完全背包做法:

#include<stdio.h>
int dp[32768];
int main()
{int i,j,n;dp[0]=1;for(i=1; i<=3; i++)for(j=i; j<32768; j++)dp[j]+=dp[j-i];while(scanf("%d",&n)!=EOF){printf("%d\n",dp[n]);}return 0;
}

递推:

http://hi.baidu.com/shenghao_200/item/6df741079aba53db1ef0465c

http://wenwen.soso.com/z/q181589609.htm

#include<stdio.h>
int a[32768];
int main()
{int n,i;a[0]=0;for(i = 1 ; i < 32768 ; i++){if(i%6==1&&i!=1)a[i]=a[i-1]+(i/6);else a[i]=a[i-1]+(i/6+1);}while(scanf("%d",&n)!=EOF)printf("%d\n",a[n]);return 0;
}

母函数:

定义母函数

G(x)=(1+x+x2+x3+…)*( 1+x2+x4+x6+…)*( 1+x3+x6+x9+…)

将其展开取相应指数项的系数即可(指数代表钱的面值,系数代表方案数)

#include<stdio.h>
#define max 32768
int ans[max],ans2[max],ans3[max];
int main()
{int i,j,n;for(i=0; i<max; i++)ans[i]=1;for(i=0; i<max; i++)for(j=0; i+j<max; j+=2)ans2[i+j]+=ans[i];for(i=0; i<max; i++)for(j=0; i+j<max; j+=3)ans3[i+j]+=ans2[i];while(scanf("%d",&n)!=EOF)printf("%d\n",ans3[n]);return 0;
}


这篇关于hdu1284 sdut2777 钱币兑换问题(完全背包,递推,母函数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1063951

相关文章

SpringBoot 异常处理/自定义格式校验的问题实例详解

《SpringBoot异常处理/自定义格式校验的问题实例详解》文章探讨SpringBoot中自定义注解校验问题,区分参数级与类级约束触发的异常类型,建议通过@RestControllerAdvice... 目录1. 问题简要描述2. 异常触发1) 参数级别约束2) 类级别约束3. 异常处理1) 字段级别约束

Python错误AttributeError: 'NoneType' object has no attribute问题的彻底解决方法

《Python错误AttributeError:NoneTypeobjecthasnoattribute问题的彻底解决方法》在Python项目开发和调试过程中,经常会碰到这样一个异常信息... 目录问题背景与概述错误解读:AttributeError: 'NoneType' object has no at

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map

nginx中端口无权限的问题解决

《nginx中端口无权限的问题解决》当Nginx日志报错bind()to80failed(13:Permissiondenied)时,这通常是由于权限不足导致Nginx无法绑定到80端口,下面就来... 目录一、问题原因分析二、解决方案1. 以 root 权限运行 Nginx(不推荐)2. 为 Nginx

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)