HDU-1028 整数划分

桃扇骨 2023-06-30 01:35 32阅读 0赞

杭电上的一道基础的母函数的题目  
这里介绍用递归加记忆化的方式完成  
参考博客: [https://www.bbsmax.com/A/kmzLnaXW5G/][https_www.bbsmax.com_A_kmzLnaXW5G]

**这里首先定义 F(n,m) 为将整数N 划分为一系列整数的和,其中最大的加数不超过M**  
根据题目意思, 1<=N<=120;  
有以下几种情况

*  N=1 或 M=1  
    这时,划分的情况只能是 1 或者 1+1+1+1+1…  
    **F(1,1)=F(1,M)=F(N,1)=1**
 *  N<M  
    显然,划分的情况只能是 N=N 这一种情况  
    **F(N,M)=F(N,N)=1**
 *  N==M

1.  当加数包含 M 时，只有一种情况 N=N
2.  当加数不包含 M 时 ，F(N,M)=F(N,M-1)
    
    **F(N,M)=F(N,M-1)+1**

*  N>M

1.  当加数包含 M 时， N=M+X1\+X2\+…  
    **F(N,M)=F(N-M,M)=F(N-M,N-M)**
2.  当加数不包含 M 时 ，F(N,M)=F(N,M-1)  
    **F(N,M)=F(N,M-1)**

## 附上代码: ##

#include<bits/stdc++.h>
    #define MAXM 131
    using namespace std;
    
    int num[MAXM][MAXM] ; 
    
    int solve(int n,int m)
    { 
    	if(m==1 || n==1 )
    	{ 
    		if(num[n][m]==-1) return num[n][m]=1;
    		else return num[n][m];
    	}
    	else if(m>n)
    	{ 
    		if(num[n][m]==-1) return num[n][m]=solve(n,n);
    		else return num[n][m];		
    	}
    	else if(n==m) { 
    		if(num[n][m]==-1) return num[n][m]=solve(n,m-1)+1;
    		else return num[n][m];		
    	}
    	else { 
    		if(num[n][m]==-1) return num[n][m]=solve(n,m-1)+solve(n-m,m);
    		else return num[n][m];	
    	}
    }
    
    int main()
    { 
    	int n;
    	while(~scanf("%d",&n))
    	{ 
    		memset(num,-1,sizeof(num));//初始化数组为-1
    		printf("%d\n",solve(n,n));
    	}
    	return 0;
    }

[https_www.bbsmax.com_A_kmzLnaXW5G]: https://www.bbsmax.com/A/kmzLnaXW5G/

发表评论取消回复

表情：

评论列表（有 0 条评论，32人围观）

还没有评论，来说两句吧...

相关阅读

相关整数划分问题

根据n和m的关系，考虑以下几种情况：（1）当 n = 1 时，不论m的值为多少（m > 0 )，只有一种划分即 \{ 1 \}; (...

墨蓝/ 2024年04月18日 16:42/ 0 赞/ 163 阅读

相关整数划分问题

题目描述计算将一个给定的正整数划分为一系列正整数的和的方案数，称为整数的划分问题，例如，当给定正整数为6时，可以有如下划分： 6=6； 6=5+1； 6=4+2=4+

清疚/ 2023年10月18日 12:19/ 0 赞/ 154 阅读

相关 HDU-1028 整数划分

杭电上的一道基础的母函数的题目这里介绍用递归加记忆化的方式完成参考博客: [https://www.bbsmax.com/A/kmzLnaXW5G/][https_

桃扇骨/ 2023年06月30日 01:35/ 0 赞/ 33 阅读

相关 hdu 1028

![博客图片][format_png] 题目链接 [hdu1028][] 题目概述求一个整数 N N N的可重无序拆分. 解题思路稍加变换,原问题等

电玩女神/ 2023年02月26日 10:28/ 0 赞/ 102 阅读

相关 HDU 1028-Ignatius and the Princess III（拆分整数-母函数-无限次）

Ignatius and the Princess III Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65

比眉伴天荒/ 2022年09月25日 01:25/ 0 赞/ 81 阅读

相关区间dp（整数划分，石子划分）

整数划分（四）链接： [http://acm.nyist.net/JudgeOnline/problem.php?pid=746][http_acm.nyist.net

ゞ浴缸里的玫瑰/ 2022年09月18日 13:56/ 0 赞/ 301 阅读

相关 hdu 1028 对某个数n的m划分数

Ignatius and the Princess III Time Limit: 2000/1000 MS (Java/Others) Memory Limit:

末蓝、/ 2022年08月03日 15:56/ 0 赞/ 204 阅读

相关整数划分问题

问题描述：将以正整数n表示成一系列正整数之和。输入：整数N 输出：划分方法的总数。 //n为输入的整数，不同划分中最大加数不超过m，返回划分方法的总数。 int q(

小咪咪/ 2022年07月14日 16:13/ 0 赞/ 260 阅读

相关整数划分--DP

5. [数的划分][Link 1] 问题描述　　将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。　　例如：n=7，k=3，下面三种分法被认为是相同

红太狼/ 2022年05月29日 10:59/ 0 赞/ 309 阅读

相关整数划分 dp

蒜头君特别喜欢数学。今天，蒜头君突发奇想：如果想要把一个正整数 nn 分解成不多于 kk 个正整数相加的形式，那么一共有多少种分解的方式呢？蒜头君觉得这个问题实在是太难了，

柔情只为你懂/ 2022年05月27日 23:26/ 0 赞/ 297 阅读