< 返回

# Problem A

##### 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));
}

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. }

/template/Home/Dawn/PC/Static