POJ 1664 放苹果 C++版

发表于 更新于

题目链接：http://poj.org/problem?id=1664

简单的题虽然代码简单，但是思路不简单，这样的题适合初学者，比如我，哈哈

解释下思路，递归求解，dj函数返回，m苹果还剩n个空盘子的情况每当只有一个空盘子，或者没有苹果的之后情况唯一，当苹果少于盘子的时候，多于的盘子永远装不满，转换为m个苹果放m盘子的情况，一半情况就是m<n的情况，可以分两种情况，也就是m-n个苹果还剩n个空盘子，和m个苹果，省n-1个空盘子的状况！

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/***************************************
Problem: 1664		User: awq123
Memory: 248K		Time: 0MS
Language: C++		Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int dj(int m,int n)
{
	if(m==0||n==1)
		return 1;
	if(m<n)
		return dj(m,m);
	else
		return dj(m-n,n)+dj(m,n-1);
}

int main()
{
	int t,m,n;
	cin>>t;
	while (t--)
	{
		cin>>m>>n;
		cout<<dj(m,n)<<endl;
	}

}