首页 > 代码库 > HDU 1028
HDU 1028
整数划分问题是将一个正整数n拆成一组数连加并等于n的形式，且这组数中的最大加数不大于n。
如6的整数划分为
6
5 + 1
4 + 2, 4 + 1 + 1
3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1
共11种。下面介绍一种通过递归方法得到一个正整数的划分数。
递归函数的声明为 int split(int n, int m);其中n为要划分的正整数，m是划分中的最大加数(当m > n时，最大加数为n)，
1 当n = 1或m = 1时，split的值为1，可根据上例看出，只有一个划分1 或 1 + 1 + 1 + 1 + 1 + 1
可用程序表示为if(n == 1 || m == 1) return 1;
2 下面看一看m 和 n的关系。它们有三种关系
(1) m > n
在整数划分中实际上最大加数不能大于n，因此在这种情况可以等价为split(n, n);
可用程序表示为if(m > n) return split(n, n);
(2) m = n
这种情况可用递归表示为split(n, m - 1) + 1，从以上例子中可以看出，就是最大加
数为6和小于6的划分之和
用程序表示为if(m == n) return (split(n, m - 1) + 1);
(3) m < n
这是最一般的情况，在划分的大多数时都是这种情况。
从上例可以看出，设m = 4，那split(6, 4)的值是最大加数小于4划分数和整数2的划分数的和。
因此，split(n, m)可表示为split(n, m - 1) + split(n - m, m)
但这里 n 的值比较大，直接递归会TLE，我们只需把过程值记住就可以解决TLE问题
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <time.h> 6 #include <ctype.h> 7 #include <string> 8 #include <queue> 9 #include <set>10 #include <map>11 #include <stack>12 #include <vector>13 #include <algorithm>14 #include <iostream>15 #define PI acos( -1.0 )16 using namespace std;17 typedef long long ll;18 19 const int NO = 125;20 int a[NO][NO];21 int n;22 23 int sum( int x, int y )24 {25 if( a[x][y] != -1 ) return a[x][y];26 if( x <= 0 || y <= 0 ) return a[x][y] = 0;27 if( y > x ) return a[x][y] = sum( x, x );28 if( x == 1 || y == 1 ) return a[x][y] = 1;29 if( x == y ) return a[x][y] = sum( x, y-1 ) + 1;30 return a[x][y] = sum( x, y-1 ) + sum( x-y, y );31 }32 33 int main()34 {35 memset( a, -1, sizeof( a ) );36 while( ~scanf( "%d", &n ) )37 {38 int ans = sum( n, n );39 printf( "%d\n", ans );40 }41 return 0;42 }
当然这题我们也可以用母函数求解
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <time.h> 6 #include <ctype.h> 7 #include <string> 8 #include <queue> 9 #include <set>10 #include <map>11 #include <stack>12 #include <vector>13 #include <algorithm>14 #include <iostream>15 #define PI acos( -1.0 )16 using namespace std;17 typedef long long ll;18 19 const int NO = 120;20 int a[NO+5], b[NO+5];21 int n;22 23 void init()24 {25 for( int i = 0; i <= NO; ++i )26 {27 a[i] = 1;28 b[i] = 0;29 }30 for( int i = 2; i <= NO; ++i )31 {32 for( int j = 0; j <= NO; ++j )33 for( int t = 0; j+t <= NO; t+=i )34 b[j+t] += a[j];35 for( int j = 0; j <= NO; ++j )36 {37 a[j] = b[j];38 b[j] = 0;39 }40 }41 }42 43 int main()44 {45 init();46 while( ~scanf( "%d", &n ) )47 {48 printf( "%d\n", a[n] );49 }50 return 0;51 }
HDU 1028