程序员人生网站导航

POJ - 1664 放苹果

栏目：php教程时间：2016-12-05 14:00:45

题目：

Description

把M个一样的苹果放在N个一样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同1种分法。

Input

第1行是测试数据的数目t（0 <= t <= 20）。以下每行均包括2个整数M和N，以空格分开。1<=M，N<=10。

Output

对输入的每组数据M和N，用1行输出相应的K。

Sample Input

1 7 3

Sample Output

这个题目自然是递归，但是否是所有人的递归式都是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; }

------分隔线----------------------------

上一篇 ceil和floor函数的编程实践

下一篇 七牛技术总监肖勤：微服务架构实践经验分享

------分隔线----------------------------