NYOJ 571整数划分(三)【DP】

整数划分(三)

时间限制：1000ms | 内存限制：65535KB

难度：3

描述

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

输入

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

输出

对于输入的 n,k;

第一行： 将n划分成若干正整数之和的划分数。

第二行： 将n划分成k个正整数之和的划分数。

第三行： 将n划分成最大数不超过k的划分数。

第四行： 将n划分成若干个 奇正整数之和的划分数。

第五行： 将n划分成若干不同整数之和的划分数。

第六行： 打印一个空行

样例输入

5 2

样例输出

7
2
3
3
3


输出提示:
1.将5划分成若干正整数之和的划分为： 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
2.将5划分成2个正整数之和的划分为： 3+2, 4+1
3.将5划分成最大数不超过2的划分为： 1+1+1+1+1, 1+1+1+2, 1+2+2
4.将5划分成若干 奇正整数之和的划分为： 5, 1+1+3, 1+1+1+1+1
5.将5划分成若干不同整数之和的划分为： 5, 1+4, 2+3

这两天搞动态规划搞得头疼，关键是自己的做题太少，思维容量太小，见到题目，不能够很快的有一个思路，导致自己像无头苍蝇一样，看来以后还得多多刷题，多多AC，只有量的积累，才有质的飞跃，加油。

看了两天的整数划分，NYOJ上的（一）（二）以前写过，用的是递归，看的是结题报告，朦朦胧胧的，这次无意间在网上看到这个题，就尝试着写了一遍，艾玛，惨不忍睹啊，然后搜了无数大牛的博客后，终于找到了一点思路，然后，按照这个思路往下写，终于看起来像那么回事了

思路:

dp[i][j]表示要被分的数为i,最大数不超过j的划分数.

当 j>i时当然是只能j分到i而已.

当i>=j时，注意到5=5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1,5可以划分为4+1,而4的划分数之前已求出,相当于加上4的划分数,即dp[i][j-1];

另外注意到5=2+2+1=2+1+1+1=1+1+1+1+1，即还要加上要减的数5减掉2之后,dp[5][2]=dp[5-2][2]+dp[5][1]=dp[3][2]+1=dp[3-2][2]+dp[3][1]+1=dp[1][1]+1+1=3;

每次算dp时其实都可以先写写dp之间的转移关系，弄清楚后，再写出状态转移方程

所以,对于前三行,根据状态转移方程很容易写出：

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]其中dp[i][j-1]为不选择j时的方案,dp[i-j][j-1]为选择j时的方案

为了加深对本题的理解，以及对DP的理解，我把这个题目上传到了我们学校的OJ上了，欢迎大家来练习~~

题目地址:http://acm.nyist.net/JudgeOnline/problem.php?pid=571

我的代码:

#include <stdio.h>
#define N 52
int dp[N][N] = {0} , dp1[N][N] = {0}  , dp2[N][N] = {0} ;
void  Divid(){
      dp[0][0] = 1 ;
      for( int i = 0 ; i < N ; i++ )
            for( int j = 1 ; j < N ; j++ ){
                  if( i < j )
                        dp[i][j] = dp[i][i] ;
                  else
                        dp[i][j] = dp[i-j][j] + dp[i][j-1] ;
            }
}
void Divid1(){
      for( int i = 1 ; i < N ; i++ )
            dp1[i][1] = 1 ;           //最大值为1时只能有本身组成,Answer为1
      for( int i = 1 ; i < N ; i+=2 )
            dp1[0][i] = 1 ;
      dp1[0][0] = 1 ;
      for( int i = 1 ; i < N ; i++ )
            for( int j = 3 ; j < N ; j+=2 ){
                  if( j > i ){
                        if( i&1 )
                              dp1[i][j] = dp1[i][i] ;
                        else
                              dp1[i][j] = dp1[i][i-1] ;
                  }
                  else
                        dp1[i][j] = dp1[i-j][j] + dp1[i][j-2] ;
            }
}
void Divid2(){
      for( int i = 1 ; i < N ; i++ ){
            dp2[0][i] = 1 ;
            dp2[1][i] = 1 ;
      }
      for( int i = 2 ;i < N ; i++ )
            for( int j = 1 ;j < N ; j++ ){
                  if( j > i )
                        dp2[i][j] = dp2[i][i] ;
                  else
                        dp2[i][j] = dp2[i-j][j-1] +dp2[i][j-1] ;
            }
}
int main(){
      int n , k ;
      Divid() ;
      Divid1() ;
      Divid2() ;
      while( ~scanf( "%d%d" , &n , &k ) ){
            printf( "%d\n" , dp[n][n] ) ;
            printf( "%d\n" , dp[n-k][k] ) ;
            printf( "%d\n" , dp[n][k]) ;
            printf( "%d\n" , n&1 ? dp1[n][n] : dp1[n][n-1] ) ;
            printf( "%d\n\n" , dp2[n][n]) ;
      }
      return 0;
}