整数划分(三)

描述

整数划分是一个经典的问题。请写一个程序,完成以下要求。

输入

每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)

输出

对于输入的 n,k;
第一行：将n划分成若干正整数之和的划分数。
第二行：将n划分成k个正整数之和的划分数。
第三行：将n划分成最大数不超过k的划分数。
第四行：将n划分成若干个奇正整数之和的划分数。
第五行：将n划分成若干不同整数之和的划分数。
第六行：打印一个空行

样例输入

5 2

样例输出

7
2
3
3
3
解题思路：
dp[i][j] = dp[i][i] (j>i)
         = dp[i-j][j] + dp[i][j-1] (i<=j)

第一行:将n划分成若干正整数之和的划分数。 dp[n][n] ;

第二行:将n划分成k个正整数之和的划分数。 dp[n-k][k] ;

第三行:将n划分成若干最大不超过k的正整数之和的划分数。 dp[n][k] ;

第四行：将n划分成若干奇正整数之和的划分数。 dp[i][j]是当前的划分数为i,最大值为j时的中的划分数，则状态转移方程为

dp[i][j] = dp[i][i] if( j>i && j%2 == 1)= dp[i][i-1] if( j>i && j%2 == 0)(最大数不可能为偶数)= dp[i-j][j] + dp[i][j-2]

没用到j时划分不变，即dp[i][j-2],用到则是dp[i-j][j];

第五行：将n划分成若干完全不同正整数之和的划分数。其实这个就是一个背包,状态转移方程为:

dp[i][j] = dp[i][j-1]+dp[i-j][j-1]

参考划分问题

 1 #include "stdafx.h"
 2 #include <iostream>
 3 using namespace std;
 4 #define N 51
 5 int dp[N][N]={0},dp1[N][N]={0},dp2[N][N]={0};
 6 void divid(){
 7     dp[0][0]=1;
 8     for(int i=0;i<N;i++)
 9         for(int j=1;j<N;j++){
10             if(i<j)
11                 dp[i][j]=dp[i][i];
12             else
13                 dp[i][j]=dp[i-j][j]+dp[i][j-1];
14         }
15 }
16 void divid1(){
17     for( int i = 1 ; i < N ; i++ )
18         dp1[i][1] = 1 ;           
19     for( int i = 1 ; i < N ; i+=2 )
20         dp1[0][i] = 1 ;
21     dp1[0][0] = 1 ;
22     for( int i = 1 ; i < N ; i++ )
23         for( int j = 3 ; j < N ; j+=2 )
24         {
25             if( j > i )
26             {
27                 if( i&1 )
28                     dp1[i][j] = dp1[i][i] ;
29                 else
30                     dp1[i][j] = dp1[i][i-1] ;
31             }
32             else
33                 dp1[i][j] = dp1[i-j][j] + dp1[i][j-2] ;
34         }
35 }
36 void divid2(){
37     for( int i = 1 ; i < N ; i++ )
38     {
39         dp2[0][i] = 1 ;
40         dp2[1][i] = 1 ;
41     }
42     for(int i=0;i<N;i++)
43         for(int j=1;j<N;j++)
44         {
45             if(i<j)
46                 dp2[i][i]=dp2[i][i];
47             else
48                 dp2[i][j]=dp2[i-j][j-1]+dp2[i][j-1];
49         }
50 }
51 int _tmain(int argc, _TCHAR* argv[])
52 {
53     divid();
54     divid1();
55     divid2();
56     int n,k;
57     while( ~scanf( "%d%d" , &n , &k ) )
58     {
59         printf( "%d
" , dp[n][n] ) ;
60         printf( "%d
" , dp[n-k][k] ) ;
61         printf( "%d
" , dp[n][k]) ;
62         printf( "%d
" , n&1 ? dp1[n][n] : dp1[n][n-1] ) ;
63         printf( "%d
" , dp2[n][n]) ;
64     }
65     return 0;
66 }

View Code