|
|
本帖最后由 这个显卡不太冷 于 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;
- }
文中部分思路借鉴网络。加入了个人的一些理解，方便大家能看懂。
|
评分
-
1
查看全部评分
-
|
发表于 2016-8-17 13:12:52
楼主
发表于 2017-1-25 17:32:13
发表于 2019-4-28 11:02:56