/*（很神奇的题目）一开始我以为是母函数的问题，的确用母函数可以解，可是铁定超时，后来baidu后发现如下解法
#include<iostream>
#include<cstdio>
using namespace std;
int a[32768];
int main()
{
int n,i;
a[0]=0;
for( i = 1 ; i < 32768 ; i++ )
{
if(i%6==1&&i!=1)
a[i]=a[i-1]+(i/6);
else
a[i]=a[i-1]+(i/6+1);
}
while(scanf("%d",&n)!=EOF)
printf("%d/n",a[n]);
return 0;
}
if(i%6==1&&i!=1)
a[i]=a[i-1]+(i/6);
else a[i]=a[i-1]+(i/6+1);
这个通式。
他是一个递推的公式，
首先，a[i]=a[i-1]这一步其实是在a[i]的基础上每种情况加上一个1分的硬币，
然后：(i/6)或者(i/6+1); 就是不包含1分硬币的情况，为什么i%6==1&&i!=1就不用加1呢？i!=1的时候不用说你也明白吧.。我来说说i%6==1的情况，你看2，3分的硬币，可以组合成2，3，4，5，6(0)分的吧，所以当在i%6==1的时候就没有组合了，其他的i%6==2，i%6==3，i%6==4，i%6==5都会有且只有一种组合组成它吧，所以都要加1。
最后我再回过头讲(i/6)，除以6是因为当大于6 的数都可以写成n*6+k吧，而每一个k都会有一种组合与他相配，当然除了k=1的时候没有，所以i/6就是n，n就是（6*n）分由2和3分的硬币组合成的种数m减去1，为什么减去1呢，因为（6*n）的情况其实就是上面然后部分说的那个情况。至于为甚麽那么巧n就等于m-1，我也没想清楚，但是你可以写出数据看看，它就是这样。
钱币兑换问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1425 Accepted Submission(s): 679
Problem Description
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input
每行只有一个正整数N，N小于32768。
Output
对应每个输入，输出兑换方法数。
Sample Input
2934
12553
Sample Output
718831
13137761
*/
#include<iostream>
#include<cstdio>
using namespace std;
const int ff = 32768;
int c1[ff];
int c2[ff];
int main()
{
int n, i, j, k;
while(cin>>n)
{
memset(c1, 0 , sizeof(c1));
memset(c2, 0 , sizeof(c2));
c1[0] = 1;
for(i = 1; i <= 3; i++)
{
for(j = 0; j <= n; j++)
for(k = 0; k + j <= n; k += i)
{
if(c1[j])
c2[ j + k] += c1[j];
}
for(k = 0; k <= n; k++)
{
c1[k] = c2[k];
c2[k] = 0;
}
}
printf("%d/n", c1[n]);
}
}