HDU 1284 钱币兑换问题 母函数、DP
2024-10-01 19:29:07
题目链接:HDU 1284 钱币兑换问题
钱币兑换问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5467 Accepted Submission(s): 3123
Problem Description
在一个国家仅有1分,2分。3分硬币,将钱N兑换成硬币有非常多种兑法。请你编程序计算出共同拥有多少种兑法。
Input
每行仅仅有一个正整数N。N小于32768。
Output
相应每一个输入,输出兑换方法数。
Sample Input
2934
12553
Sample Output
718831
13137761
Author
SmallBeer(CML)
Source
Recommend
lcy | We have carefully selected several similar problems for you:
pid=2159" style="color:rgb(26,92,200); text-decoration:none">2159
pid=1248" style="color:rgb(26,92,200); text-decoration:none">1248
pid=1203" style="color:rgb(26,92,200); text-decoration:none">1203
1231 1249思路1:母函数思想,求系数
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; #define maxn 32770
int n, c1[maxn], c2[maxn];
void Init()
{
for(int i = 0; i <= maxn; i++)
{
c1[i] = 1;
c2[i] = 0;
}
for(int i = 2; i <= 3; i++)
{
for(int j = 0; j <= maxn; j++)
for(int k = 0; k+j <= maxn; k+=i)
c2[j+k] += c1[j];
for(int j = 0; j <= maxn; j++)
{
c1[j] = c2[j];
c2[j] = 0;
}
}
}
int main()
{
Init();
while(~scanf("%d", &n))
printf("%d\n", c1[n]);
return 0;
}
思路2:DP,后面的钱能够由前面的钱推出。
代码:
#include <iostream>
#include <cstdio>
using namespace std; #define maxn 32770
int n, dp[maxn];
void Init()
{
dp[0] = 1;
for(int i = 1; i <= 3; i++)
for(int j = i; j <= maxn; j++)
dp[j] += dp[j-i];
}
int main()
{
Init();
while(~scanf("%d", &n))
printf("%d\n", dp[n]);
return 0;
}
最新文章
- utf-8 汉字对照表
- C语言 第六章 多重循环练习
- 在Ubuntu14.04_ROS_indigo上安装Kinect2驱动和bridge
- Java/JavaWeb中读取资源文件
- 2016年12月25日 星期日 --出埃及记 Exodus 21:20
- NSString字符串
- 读书笔记——Windows环境下32位汇编语言程序设计(13)关于EXCEPTION_DEBUG_INFO结构体
- 关于NGUI制作图集在低内存设备上的注意事项
- php 获取客户端IP地址
- 笨方法学python--打印
- Oracle基础学习(二)v$session中Command的数字含义
- Ubuntu离线安装VSCode(附带前期准备工作)
- 『vue踩坑日常』 在index.html中引入静态文件不生效
- Python运算符——复合运算符
- 改变eclipse默认的Tomcat部署路径
- solvepnp
- python---自定义分页类
- 物联网架构成长之路(13)-SpringBoot入门
- 设计模式之Adapter(适配器)(转)
- excel表格如何打斜杠