hdu1028

Problem A

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 5   Accepted Submission(s) : 4

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

4 10 20

 

Sample Output

5 42 627

 

 

(转载)：

 

整数划分的递归算法：

int split(int n, int m)
{
 if(n < 1 || m < 1)
  return 0;
 if(n == 1 || m == 1)
  return 1;
 if(n < m) 
  return split(n, n);
 if(n == m) 
  return (split(n, m - 1) + 1);
 if(n > m)
  return (split(n, m - 1) + split((n - m), m));
}

递归算法易于理解。但是由于多次重复计算，会很浪费时间。所以需要转化成非递归的算法。如下：

 

首先，我们引进一个小小概念来方便描述吧，record[n][m]是把自然数划划分成所有元素不大于m的分法，例如：

当n=4，m=1时，要求所有的元素都比m小，所以划分法只有1种：{1，1，1，1}；

当n=4，m=2时，。。。。。。。。。。。。。。。。只有3种{1，1，1，1},{2，1，1}，{2，2}；

当n=4，m=3时，。。。。。。。。。。。。。。。。只有4种{1，1，1，1},{2，1，1}，{2，2},{3,1}；

当n=4，m=5时，。。。。。。。。。。。。。。。。只有5种{1，1，1，1},{2，1，1}，{2，2},{3,1},{4}；

从上面我们可以发现：当n==1||m==1时，只有一种分法；

当n<m时，由于分法不可能出现负数，所以record[n][m]=record[n][n];

当n==m时，那么就得分析是否要分出m这一个数，如果要分那就只有一种{m}，要是不分，那就是把n分成不大于m-1的若干份；即record[n][n]=1+record[n][n-1];

当n>m时，那么就得分析是否要分出m这一个数，如果要分那就{{m},{x1,x2,x3..}}时n-m的分法record[n-m][m]，要是不分，那就是把n分成不大于m-1的若干份；即record[n][n]=record[n-m][m]+record[n][m-1];

 

 

 

代码：

1. #include<iostream>
2. using namespace std;
3. int dp[150][150]={0}; 
4. int main()
5. {
6.     int i,j;
7.     for(i=1;i<=121;i++)
8.   dp[1][i]=dp[i][1]=1;
9.     for(i=2;i<121;i++)
10.     {
11.         for(j=2;j<=121;j++)
12.         {
13.             if(i<j) 
14.     dp[i][j]=dp[i][i];
15.             else if(i==j)
16.     dp[i][j]=1+dp[i][j-1];
17.             else if(i>j) 
18.     dp[i][j]=dp[i-j][j]+dp[i][j-1];
19.         }
20.     }
21.     int n;
22.     while(cin>>n)
23.   cout<<dp[n][n]<<endl;
24.     return 0;
25. }

1. #include <iostream>
2. using namespace std;
3. const int lmax=10000;   
4. int c1[lmax],c2[lmax];
5. int main()
6. {
7.  int n,i,j,k;
8.  while (cin>>n)
9.  {
10.   for (i=0;i<=n;i++)
11.    {
12.    c1[i]=0;
13.    c2[i]=0;
14.   }
15.    for(i=0;i<=n;i++)
16.     c1[i]=1;
17.    for(i=2;i<=n;i++)
18.    {
19.     for(j=0;j<=n;j++)
20.      for(k=0;k+j<=n;k+=i)
21.      {
22.       c2[j+k]+=c1[j]; 
23.      }
24.      for (j=0;j<=n;j++)
25.      { 
26.       c1[j]=c2[j];
27.       c2[j]=0;
28.      }
29.    }
30.    cout<<c1[n]<<endl;
31.  }
32.  return 0;
33. }