POJ – 1664 放苹果

题目:

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

8

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

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » POJ – 1664 放苹果

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡