Poj 1664
题意
中文题。。。略了
思路
没做出来,上网查了之后发现用递归的思想。
分为两种情况
1.至少一个盘子空着 则该问题简化为n-1个盘子,m个苹果
2.每个盘子至少一个苹果,那剩下的苹果的放法则为n
个盘子,m-n个苹果。
一直递归 到苹果的数量为0,则只有1种情况。
盘子为1的时候,也只有1种放法。
当盘子比苹果多的时候,则都为m个盘子和m苹果放法一样。
#include <iostream>
#include <stdio.h>
using namespace std;
int count(int m, int n){
if(m == 0||n ==1)
return 1;
if(m<n)
return count(m,m);
return count(m - n,n) +count(m, n-1);
}
int main(int argc, char const *argv[])
{
int t,m,n;
cin>>t;
while(t--){
cin>>m>>n;
cout<<count(m,n)<<endl;
}
return 0;
}
网友评论