HDU-1028-Ignatius and the Princess III

HDU-1028-Ignatius and the Princess III

http://acm.hdu.edu.cn/showproblem.php?pid=1028

整数划分，无奈，超时

#include<stdio.h>
int huafen(int n,int m)//将n分为最大加数不超过m
{
	if(n<1||m<1)
	return 0;
	if(n==1||m==1)
	return 1;
	if(n<m)
	return huafen(n,n);
	if(n==m)
	return huafen(n,m-1)+1;
	return huafen(n,m-1)+huafen(n-m,m);  //最大加数==m和最大加数<=m-1的划分构成
}
int main()
{
	int t;
	while(scanf("%d",&t)!=EOF)
	printf("%d\n",huafen(t,t));
	return 0;
}

参考了TankyWoo大牛的博客，原来用母函数也能解决整数划分问题

给个例子

有1克、2克、3克、4克的砝码各一 枚，能称出哪几种重量？每种重量各有几种可能方案？

1个1克的砝码可以用函数1+x表示

1个2克的砝码可以用函数1+x^2表示

1个3克的砝码可以用函数1+x^3表示

1个4克的砝码可以用函数1+x^4表示

(1+x)(1+x^2)(1+x^3)(1+x^4)

=(1+x+x^2+x^3)(1+x^3+x^4+x^7)

=1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^10

例如右端有2x^5 项，即称出5克的方案有2：5=3+2=4+1；同样6=1+2+3=4+2；10=1+2+3+4。

故称出6克的方案有2，称出10克的方案有1

由此可以构造整数划分的函数

G(x)=(1+x+x^2+……)*(1+x^2+x^4…..)*(1+x^3+x^6…….)*…….

只要模拟多项式相乘即可，求出x^n的系数

#include<stdio.h>
int c1[10001],c2[10001];
int main()
{
	int n,i,j,k;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<=n;i++)
		{
			c1[i]=1;
			c2[i]=0;
		}
		for(i=2;i<=n;i++)
		{
			for(j=0;j<=n;j++)
			for(k=0;k+j<=n;k+=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;
}