钱币兑换问题
Problem Description
在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input
每行只有一个正整数N,N小于32768。
Output
对应每个输入,输出兑换方法数。
Sample Input
Sample Output
Author
SmallBeer(CML)
Source
Recommend
lcy
直接发代码:
/*
//典型的穷举法
#include<iostream>
using namespace std;
int main()
{
int x,y,z,n;
int num;
while(cin>>num && num>0)
{
n=0;
for(x=0;x<=num;x++)
for(y=0;y<=num/2;y++)
for(z=0;z<=num/3;z++)
if(x+2*y+3*z==num)
n++;
cout<<n<<endl;
}
return 0;
}
*/
//上面的穷举法太慢,我的电脑足足跑了30秒才有答案,坑啊!
//套用母函数模版
#include<iostream>
using namespace std;
const int MAX=32768;
int c1[MAX+1],c2[MAX+1];
int main()
{
int n,j,i,k,num;
for(i=0;i<=MAX;i++)
{
c1[i]=1;c2[i]=0;
}
for(i=2;i<=3;i++)
{
for(j=0;j<=MAX;j++)
for(k=0;k+j<=MAX;k=k+i)
{
c2[j+k]+=c1[j];
}
for(j=0;j<=MAX;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
while(scanf("%d",&num)!=EOF)
{
printf("%d\n",c1[num]);
}
return 0;
}
分享到:
相关推荐
杭电oj1000题解题报告
杭电OJ题目分类的叙述,可以方便去学习去做。
杭电OJ 2028代码 the rosolve of the hdu 2028
本资源主要提供了杭电oj题目分类和自测状况两大类 可实现随机选题等功能.
杭电OJ(1000-1099) AC 代码
杭电OJ部分威士忌的代码 杭电OJ部分威士忌的代码杭电OJ部分威士忌的代码
杭电oj上的一些疑问,适用于初学者,可以解答一些疑问 都是一些水题
杭电oj 1047习题
杭电oj分类
杭州电子科技大学 oj离线版
这是HDUOJ上面的140道题目的答案,其中大部分都是简单题,有些太简单的就没有收集进去,代码为C/C++,全都AC了的,其中有些有具体的说明是怎么做的,例如博弈论那些
杭电oj的离线版以及题目分类的文档 更加一目了然 方便选择适合的题目做 适合暂时上不了网的用于练习
课程资源 杭电OJ1000-1099答案 ,仅供参考...
这是杭电OJ上某些题的解题报告,后续还有上传很多!
基于Laravel 5.0的OJ题解网站 , 目前涵盖安科OJ,南阳OJ,杭电OJ ,北大OJ,浙大OJ.zip
杭电oj1048答案,c++代码,适合初学者,思路简单
杭电离线oj(2010版),方便不能上网的朋友用,比别的版本增加了很多题!
杭电ACM2000-2011题已提交的代码!保证正确!