关于我们

质量为本、客户为根、勇于拼搏、务实创新

< 返回

hdu1028

发布时间:2022-07-27 13:55:59

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     (转载):   整数划分的递归算法:hdu1028

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

/template/Home/Dawn/PC/Static

选择风纳云,也许是您成就一番大事业的开端

注册账号