POJ - 1664 放苹果
来源:程序员人生 发布时间:2016-12-05 14:00:45 阅读次数:2423次
题目:
Description
把M个一样的苹果放在N个一样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同1种分法。
这个题目自然是递归,但是否是所有人的递归式都是1样的。
假定本题对应的答案是list[n][m],n,m非负,
那末首先,当n为0时list[0][i] = (i == 0);
其次,找递归式。
如果这n个盘子里面,存在空盘子,那末去掉它,就变成“把m个相同的苹果放入n⑴个相同的盘子”这个子问题了。
否则,每一个盘子都最少有1个苹果,那末去掉这n个苹果,就变成“把m-n个苹果放入n个相同的盘子”这个子问题了。
所以,递归式就是list[n][m]=list[n⑴][m]+list[n][m-n]
这个m-n必须为非负的,这1点,和0⑴背包非常相像。
准确的说,这个组合题目的子问题集的拓扑结构和0⑴背包是1样的。
也就是说,如果这个题目只有1组m,n,那末本题就不需要2维数组,只需要1维数组,便可利用0⑴背包的空间紧缩方法算出结果。详情点击打开我的博客(0⑴背包)
下面的代码,虽然没有这样,但是初始化的顺序却是1样的。
代码:
#include<iostream>
#include<stdio.h>
using namespace std;
const int l = 11;
int list[l][l];
void getList()
{
for (int i = 0; i < l; i++)list[0][i] = (i == 0);
for (int i = 1; i < l; i++)for (int j = 0; j < l; j++)
{
list[i][j] = list[i - 1][j];
if (j >= i)list[i][j] += list[i][j - i];
}
}
int main()
{
getList();
int t, m, n;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &m, &n);
printf("%d\n", list[n][m]);
}
return 0;
}
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠