NYOJ 571整数区划(三)【DP】
整数划分(三)
时间限制:1000 ms | 内存限制:65535 KB
难度:3
-
描述
-
整数划分是一个经典的问题。请写一个程序,完成以下要求。
-
输入
-
每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)
-
输出
-
对于输入的 n,k;
第一行: 将n划分成若干正整数之和的划分数。
第二行: 将n划分成k个正整数之和的划分数。
第三行: 将n划分成最大数不超过k的划分数。
第四行: 将n划分成若干个 奇正整数之和的划分数。
第五行: 将n划分成若干不同整数之和的划分数。
第六行: 打印一个空行
-
样例输入
-
5 2
-
样例输出
-
72333
输出提示:
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
整数划分(三)
整数划分是一个经典的问题。请写一个程序,完成以下要求。
- 输入
- 每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)
- 输出
-
对于输入的 n,k;第一行: 将n划分成若干正整数之和的划分数。第二行: 将n划分成k个正整数之和的划分数。第三行: 将n划分成最大数不超过k的划分数。第四行: 将n划分成若干个 奇正整数之和的划分数。第五行: 将n划分成若干不同整数之和的划分数。第六行: 打印一个空行
- 样例输入
-
5 2
- 样例输出
-
72333
输出提示: 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; }