|
本帖最后由 这个显卡不太冷 于 2016-8-17 18:52 编辑
写这个是因为今天看到一道题 ,发现了新的做法~
以下是原题目:http://noi.openjudge.cn/ch0205/666/
总时间限制: 1000ms 内存限制: 65536kB描述把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)
5,1,1和1,5,1 是同一种分法。
输入第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。输出对输入的每组数据M和N,用一行输出相应的K。
样例输入17 3
样例输出8
乍一看这题,觉得应该就是属于DFS无脑搜的类型,从每个盘子都放一个开始枚举,判断重复的方案,最后输出。虽然这道题可行,因为数据10*20不算大,1S内可以过,但是如果真的数据大了,爆搜肯定没法过。
于是,我想到了类似的问题,整数划分问题。
-----------------------------------------------------------------简陋的分割线--------------------------------------------------------------------------
那么先来了解一下什么是整数划分问题。
整数划分问题是将一个正整数m拆成一组数连加并等于m的形式,且这组数中的最大加数不大于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种
是不是觉得和放苹果问题有点像??
此类问题的正确解法是递归求解。(有点像DP)
首先设一个方法fun(m,n)表示整数m的在最大加数n的情况下的划分方案数。
1.有例子得出边界条件
当m或者n都等于1的时候(被划分数为1或者只用1来划分),只有一种方案数。
if(m==1||n==1) return 1;
2.有例子得出递归关系
(1)m=n
这种关系一般是一开始就出现的关系。
观察例子可得到方案数为“用本身划分(即只有一种)”的方案数和“不用本身划分的方案数(继续递归)”之和。
if(m==n) return 1+fun(m,n-1);
(2)m>n
紧接着出现的就是这种关系。
同样是方案数为“用最大加数划分”和“不用最大加数划分”之和。
if(m>n) return fun(m-n,n)+fun(m,n-1);
这里说明一下,用最大加数分解的话那么其中一个数就定了,就成了被划分数减去最大加数后的划分方案。
(3)m<n
如果(2)中设m=6,n=4,则可能会出现这种情况。
这种情况十分简单。因为被划分数字不能超过m。那么等价于n=m;
if(m<n) return fun(m,m);
至此,所有情况已经讨论完成,可以写代码了。
- #include <stdio.h>
- int split(int n, int m)
- {
- if(n < 1 || m < 1) return 0;
- if(n == 1 || m == 1) return 1;
- if(n < m) return split(n, n);
- if(n == m) return (split(n, m - 1) + 1);
- if(n > m) return (split(n, m - 1) + split((n - m), m));
- }
- int main()
- {
- printf("12的划分数: %d", split(12, 12));
- return 0;
- }
复制代码
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
回到最开始的问题,就变得很简单了。就像变式
设f(m,n)表示m个苹果放在n个盘子里的方案。
1.边界条件只有一个盘子或者只有一个苹果或者没有苹果(因为允许空)
if(m==1||n==1||m==0) return 1;
2.m>n
苹果数大于盘子数,则为空一个盘子和不空盘子的方案数之和(类比为用最大加数划分和不用最大加数划分之和)
if(m>n) return f(m,n-1)+f(m-n,n);
同样说明一下。因为m>n所以如果不空盘子的话,每个盘子里面放一个不会影响方案数。所以m=m-n;可以类比整数划分~~
3.m<n
反正有n-m个盘子是空的。
if(m<n) return f(m,m);
4.m=n
这种情况可以每个盘子放一个(一种方案),和f(m,n-1)的方案数之和。
通过观察,固定的一种方案必定是边界条件所以可以整合进1和2.
- #include <stdio.h>
-
- int f(int m , int n)
- {
- if(m == 1 || n== 1 || m == 0) return 1;
- if(m < n) return f(m, m);
- return f(m - n, n) + f(m, n - 1);
- }
- int main()
- {
- int n , m , z;
- scanf("%d", &z);
- while(z-- > 0)
- {
- scanf("%d%d", &m ,&n);
- printf("%d\n",f(m, n));
- }
- return 0;
- }
复制代码 代码提交上去是AC的。
文中部分思路借鉴网络。加入了个人的一些理解,方便大家能看懂。
|
评分
-
1
查看全部评分
-
|