首页 > 代码库 > POJ 1664 放苹果

POJ 1664 放苹果

传送门:https://i.cnblogs.com/EditPosts.aspx?opt=1

技术分享

解题思路:

m:苹果数量,n:盘子数量。

f(m,n):=m个苹果放在n个盘子的方案数

1.n>m

这时总会有有n-m个盘子剩下,这时问题就可以转换到  f(m,m)

2. n<=m

 这时有两种情况,每个盘子都放,然后就是把m-n个苹果放入n个盘子  f(m-n,n);

                             至少有一个盘子不放,那么就是把m个苹果放入n-1个盘子f(m,n-1);

基本情况

只有1个苹果,或0个苹果只有一种情况。

只有一个盘子时,也只有一种情况。

实现代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 
 7 //m个苹果,n个盘子
 8 int solve(int m,int n){
 9     if(n==1||m==1||m==0)
10        return 1;
11     if(n>m)
12         return solve(m,m);
13     else
14         return solve(m,n-1)+solve(m-n,n);
15 }
16 
17 int main(){
18     int T;
19     scanf("%d",&T);
20     while(T--){
21         int n,m;
22         scanf("%d%d",&m,&n);
23         cout<<solve(m,n)<<endl;
24     }
25 }

 

POJ 1664 放苹果