当前位置:首页 > 递推 > 正文
NOI2.3-666放苹果
481+

题目大意:把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

输入

第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。

输出

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

样例输入

1
7 3

样例输出

8

解题思路

不同习惯m个苹果n个盘子,不妨看成是n个苹果m个盘子,用f[n][m]来表示。下面分类讨论:

如果盘子比苹果多,即m>n,那么肯定有m-n个空盘子,空盘子没用,直接不要就行了,f[n][m] = f[n][n]。

否则m<=n,又有两种情况——要么有空盘子,要么没有空盘子,两种情况加起来就是f[n][m]:如果有空盘子(至少1个),空盘子还是不要,f[n][m] += f[n][m-1],如果没有空盘子,先每个盘子各放一个苹果,转换成n-m个苹果放到m个盘子,即f[n][m] += f[n-m][m]。

最后考虑赋初值问题。显然,只有一个盘子或者一个苹果,方案数都是1。然后再看看递推式,如果从2开始推,-1之后最小是1,已经有初值了,但是n-m是在m<=n的情况下出现的,有可能为0,故需要把f[0][1~m]赋初值。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,

NOI2.3-666放苹果:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter