首页 > 代码库 > 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 放苹果
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。