首页 > 代码库 > hdu 1028

hdu 1028

2024-07-15 17:28:35   222人阅读

Ignatius and the Princess III

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12639    Accepted Submission(s): 8929


Problem Description
"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.

"The second problem is, given an positive integer N, we define an equation like this:
  N=a[1]+a[2]+a[3]+...+a[m];
  a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
  4 = 4;
  4 = 3 + 1;
  4 = 2 + 2;
  4 = 2 + 1 + 1;
  4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
 


Input
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.
 


Output
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.
 


Sample Input
41020
 


Sample Output
542627
 


Author
Ignatius.L
 
 
用母函数来求解
母函数公式G(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+...)(1+x^3+x^6+...)
可以考虑用原始模板来求解，但是原始的模板超时，所以就直接将所有的值，给算出来，用占用较大空间的方法来缓解超时问题
原始代码如下：
#include<stdio.h>int main(){	int n,i,j,k;	int a[1010],b[1010];//这个根据题目要求灵活变化	while(~scanf("%d",&n))//要是有对n的其他限制条件也可以在此 说明 加以限制	{		for(i=0;i<=n;i++)		a[i]=1,b[i]=0;		for(i=2;i<=n;i++)		{			for(j=0;j<=n;j++)			for(k=0;k+j<=n;k+=i)			b[j+k]+=a[j];					for(j=0;j<=n;j++)			a[j]=b[j],b[j]=0;		} 		printf("%d\n",a[n]);	} 	return 0;}

 
代码如下：
<span style="font-size:14px;">#include<stdio.h>int main(){	int n;	int i,j,k;	int a[130],b[130];	for(i=0;i<=129;i++)		a[i]=1,b[i]=1;		for(i=2;i<=129;i++)		{			for(j=1;j<=129/i;j++)			{				for(k=0;k<=129;k++)					if(k+j*i<=129)					b[k+j*i]+=a[k];			}			for(j=0;j<=129;j++)			a[j]=b[j];		}	while(~scanf("%d",&n))	{		printf("%d\n",a[n]);	}	return 0;}</span>


联系
我们