hdu 1398 Square Coins （雌函数）
hdu 1398 Square Coins （母函数）
母函数。。。
与模版有点不同
模版里，物品是1，2，3，4，5，......，n
这里是1，4，9，---17^2
#include"stdio.h"
#define MAX 10000
int c1[MAX],c2[MAX];
int main()
{
int n,i,j,k;
while(scanf("%d",&n)!=-1&&n)
{
for(i=0;i<=n;i++)
{
c1[i]=1;c2[i]=0;
}
for(i=2;i<=17;i++)
{
for(j=0;j<=n;j++)
{
for(k=0;k+j<=n;k+=i*i)
c2[j+k]+=c1[j];
}
for(j=0;j<=n;j++)
{
c1[j]=c2[j];c2[j]=0;
}
}
printf("%d\n",c1[n]);
}
return 0;
}