poj 1664 放苹果(dfs)

时间:2022-04-05 01:27:28
放苹果
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 30284   Accepted: 19098

Description

把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

Input

第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。

Output

对输入的每组数据M和N,用一行输出相应的K。

Sample Input

1
7 3

Sample Output

8

分析:简单的DFS,可以把问题想象成把一个整数M分解成N个数相加,其中符合加法交换律的是一种情况。为保证不重复(即不会出现加法交换律的情况出现),可以令分解的N个数呈非递增(或非递减)顺序排列,所以下面的递归函数里,有一个参数是前一个数的大小,在本次递归里分配的数要不大于前一个数的大小。

Java AC 代码

import java.util.Scanner;

public class Main {

    static int apples;
static int plates; static int plans; public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int testNumber = sc.nextInt();
for(int i = 1; i <= testNumber; i++) {
apples = sc.nextInt();
plates = sc.nextInt();
plans = 0;
dfs(apples, plates, apples + 1);
System.out.println(plans);
}
} /**
*
* @param leftApples 剩余的苹果数
* @param leftPlates 剩余的盘子数
* @param pre 前一个盘子放的苹果数。要保证当前盘子放的苹果数小于前一个盘子放的苹果数,这样可以避免重复(当然也可以把顺序反过来放)
*/
public static void dfs(int leftApples, int leftPlates, int pre) { if(leftApples == 0 && leftPlates >=0) { //苹果没了,但盘子还有或恰好没有,则方案数加1
plans ++;
return;
} if(leftPlates <= 0)
return; for(int i = leftApples; i > 0; i--) {
if(i > pre) //如果当前盘子要放的苹果数大于前一个盘子的苹果数,则跳过
continue;
findPlans(leftApples - i, leftPlates - 1, i);
} }
}