钱币兑换问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2190 Accepted Submission(s): 1185
Problem Description
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input
每行只有一个正整数N，N小于32768。
Output
对应每个输入，输出兑换方法数。
Sample Input
2934 12553
Sample Output
718831 13137761
Author
SmallBeer(CML)
Source
先开始天真了。。以为是生成函数，于是果断TLE。。
然后后来发现这个式子其实等价于x+2y+3z=n的解的个数
这个个数是有规律的。
我用生成函数的方法打了前面100项的表，然后找到了规律，于是快速AC
我的代码：
#include<stdio.h>
int p[40000];
void init()
{
int i,j,d=1;
p[1]=1,p[2]=2,p[3]=3,p[4]=4,p[5]=5;
for(i=6;i<=32768;i++)
{
if(i%6!=0&&i%6!=1)
p[i]=p[i-1]+d;
if(i%6==0)
{
p[i]=p[i-1]+d+1;
d++;
}
if(i%6==1)
p[i]=p[i-1]+d-1;
}
}
int main()
{
int n,i;
init();
while(scanf("%d",&n)!=EOF)
printf("%d\n",p[n]);
return 0;
}
超时的暴力代码（生成函数）
#include<stdio.h>
#include<string.h>
typedef long long ll;
ll c1[40000],c2[40000];
int a[4],b[4];
int main()
{
ll n,i,j,k;
for(n=1;n<=100;n++)
{
for(i=0;i<=n;i++)
{
c1[i]=0;
c2[i]=0;
}
a[1]=1,b[1]=n;
a[2]=2,b[2]=n/2;
a[3]=3,b[3]=n/3;
c1[0]=1;
for(i=1;i<=b[1];i++)
c1[i]=1;
ll len=a[1]*b[1];
for(i=2;i<=3;i++)
{
for(j=0;j<=len;j++)
for(k=0;k<=a[i]*b[i];k=k+a[i])
c2[k+j]=c2[k+j]+c1[j];
len=len+a[i]*b[i];
for(j=0;j<=n;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
printf("%lld %lld\n",n,c1[n]);
}
return 0;
}