1192：放苹果

阳光穿透心脏的1/2处 2022-01-12 02:27 458阅读 0赞

### 1192：放苹果 ###

时间限制: 1000 ms 内存限制: 65536 KB  
提交数: 4472 通过数: 2773

### 【题目描述】 ###

把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

### 【输出样例】 ###

### 【来源】 ###

[No][]

> **核心：空盘子不影响方法总数**
> 
> 设m个苹果放进n个盘子的方法总数为f（m,n）。现在要分为两种情况，盘子数量多和苹果数量多。
> 
> 一、盘子数量多（m<n）
> 
> 盘子数量多最后至少要剩余n-m个空盘子，去掉他们对摆放苹果的方法总数不构成影响，最后最多剩余m个盘子。因此此时：
> 
> f(m,n)=f(m,m)
> 
> 二、苹果数量多（m>=n）
> 
> 当苹果的数量多于盘子的数量时，有两种情况。
> 
> （1）有空盘子
> 
> 那至少应该有一个盘子剩余：f(m,n-1)
> 
> （2）没有空盘子
> 
> 那至少每一个盘子都有一个苹果，去掉n个苹果也是多放法总数不构成影响。
> 
> f(m-n,n)
> 
> 总的方法数为：f(m,n)=f(m,n-1)+f(m-n,n)
> 
> 【边界】没有苹果或者只有一个盘子的时候

f(4,2)

f(4,1) + f(2,2)

1 种 |

f(2,1) + f(0,0)

1 种 1种

总的放法数：1+1+1=3种

> 递归代码

#include<cstdio>
    int m,n;
    int put(int m,int n)//m个苹果，n个盘子 
    {
    	if(m==0 || n == 1)
    		return 1;
    	if(m >= n)//苹果多,有盘子为空+无盘子为空 
    		return put(m,n-1)+put(m-n,n);
    	else//盘子多 
    		return put(m,m);
     } 
     
    int main()
    {
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d%d",&m,&n);
    		printf("%d\n",put(m,n));
    	}
    	return 0;
    }

> 递推代码

#include<cstdio>
    int f[15][15];
    int main()
    {
    	int t,m,n;
    	scanf("%d",&t);
    	for(int i = 0; i <= 10; ++i)//i个苹果，j个盘子,求出所有的情况 
    	{
    		for(int j = 0; j <= 10; ++j)
    		{
    			if(i == 0 || j == 1) f[i][j] = 1;
    			if(i >= j)
    				f[i][j] = f[i][j-1]+f[i-j][j];
    			else
    				f[i][j] = f[i][i]; 
    		}
    	}
    	while(t--)
    	{
    		scanf("%d%d",&m,&n);
    		printf("%d\n",f[m][n]);
    	}
    	return 0;
    }

[No]: http://ybt.ssoier.cn:8088/problem_search.php?searchsource=No