题意:在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
原题http://acm.hdu.edu.cn/showproblem.php?pid=1284
题解:用母函数暴力打表,因为钱币取值给定,是不变的,所以只有三个表达式G(x)=(1+x+x^2+x^3+……+x^MAX)(1+x^2+x^4+……+x^2*MAX)(1+x^3+x^6+……+x^3*MAX);要把循环放在外面,要不然TEL;
- #include<cstdio>
- using namespace std;
- #define MAX 32768
- int a1[MAX],a2[MAX];
- void init()//暴力打表
- {
- int i,j,k;
- for(i=0;i<MAX;i++)
- {
- a1[i]=1;
- a2[i]=0;
- }
- for(i=2;i<=3;i++)
- {
- for(j=0;j<MAX;j++)
- for(k=0;k+j<MAX;k+=i)
- a2[j+k]+=a1[j];
- for(j=0;j<MAX;j++)
- {
- a1[j]=a2[j];
- a2[j]=0;
- }
- }
- }
- int main()
- {
- init();
- int n;
- while(scanf("%d",&n)!=EOF)
- printf("%d\n",a1[n]);
- return 0;
- }