首页 > 代码库 > 钱币兑换问题(杭电1284)(母函数)
钱币兑换问题(杭电1284)(母函数)
钱币兑换问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6019 Accepted Submission(s): 3462
Problem Description
在一个国家仅有1分,2分,3分硬币。将钱N兑换成硬币有非常多种兑法。
请你编程序计算出共同拥有多少种兑法。
Input
每行仅仅有一个正整数N。N小于32768。
Output
相应每一个输入,输出兑换方法数。
Sample Input
2934 12553
Sample Output
718831 13137761
Author
SmallBeer(CML)
Source
杭电ACM集训队训练赛(VII)
#include<stdio.h> #define Max 32768 int a[35000],c[35000]; int main() { int n,i,j,k; for(i=0;i<=Max;i++) { c[i]=1; a[i]=0; } for(i=2;i<=3;i++) { for(j=0;j<=Max;j++) { for(k=0;k+j<Max;k+=i) a[k+j]+=c[j]; } for(j=0;j<Max;j++) { c[j]=a[j]; a[j]=0; } } while(scanf("%d",&n)!=EOF) { printf("%d\n",c[n]); } return 0; }
钱币兑换问题(杭电1284)(母函数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。