HDOJ 2069 Coin Change(母函数)
2024-08-24 09:43:30
Coin Change
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10289 Accepted Submission(s): 3451
Problem Description
Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.
For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, or two 5-cent coins and one 1-cent coin, or one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent.
Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 100 coins.
Input
The input file contains any number of lines, each one consisting of a number ( ≤250 ) for the amount of money in cents.
Output
For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.
Sample Input
11
26
26
Sample Output
4
13
13
Author
Lily
Source
Recommend
linle
//加一维限制数量。。。。。。 #include <iostream>
#include <cstdio>
#include <cstring> using namespace std; const int value[]={,,,,,}; int c1[][],c2[][];
int n; int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(c1,,sizeof(c1));
memset(c2,,sizeof(c2)); for(int i=;i<=min(n,);i++)
{
c1[i][i]=;
} for(int i=;i<=;i++)
{
for(int j=;j<=n;j++)
{
for(int k=;k+j<=n;k+=value[i])
{
for(int l=;l<=&&l+k/value[i]<=;l++)
{
c2[j+k][l+k/value[i]]+=c1[j][l];
}
}
} for(int j=;j<=n;j++)
{
for(int k=;k<=;k++)
{
c1[j][k]=c2[j][k];
c2[j][k]=;
}
}
} int ans=;
for(int j=;j<=;j++)
{
ans+=c1[n][j];
} printf("%d\n",ans); }
return ;
}
最新文章
- Python for Infomatics 第12章 网络编程一(译)
- 吉特仓库管理系统-.NET4.0环境安装不上问题解决
- Code Simplicity–The Science of Software Development 书摘
- EditText的一些属性及用法
- weblogic诊断案例-AdminServer平均1-2周崩溃
- [转]常用电器认证标志 &;&; 手机频段
- c++ struct 使用
- C#_在.net中序列化读写xml方法的总结
- 动态链接库DLL
- 打造最强Windows Server 2012 给你比Windows 8更好的体验
- iOS在GitHub Top 前100 简介
- 深入浅出理解python 装饰器
- Jenkins构建maven项目跳过测试用例的命令
- namecheap 添加二级域名
- c#中打开Excel文档
- 关于requests的session方法保持不了cookie的问题。(seesion的意思是保持一个会话,比如 登陆后继续操作(记录身份信息) 而requests是单次请求的请求,身份信息不会被记录)
- Android中的MVP架构分解和实现
- tf.multiply()和tf.matmul()区别
- Web自动化 - 选择操作元素 1
- ADS中编译现存项目时常见错误:无法打开文件\&hellip;\&hellip;\2440init.o的解决办法