傻人题解 | #放苹果#
放苹果
https://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf
思路：
本篇题解很适合和我一样不怎么聪明的人，虽然这是简单题，但还是难倒了我。但是这道题数据范围小，我们可以想到暴力来求解。
根据题意，不同顺序的分法记录为一种，所以可以人为的安排一种顺序。这里假设为升序（允许重复）
对于题目的例子，模拟如下：
007 016 025 034 115 123 133 223
所以我们可以直接按这个过程模拟，
- 有比较多的判断/转移，所以用递归应该比较好实现。
怎么写呢？每个位置可以枚举的数可以都先认为是0-n,那么就是，由于有顺序有约束，要减掉很大一部分。
下面我们就来写递归，按照公式化的方法，一步步写，这样一般都能搞出来。
状态定义：
表示正在枚举
个盘子,之前盘子的总和为
,上一个盘子枚举的数是
- 之所以这么定义，首先肯定有
,因为我们有顺序，所以应该有
，最后我们还需要比较和与
，所以应该有
区间是
转移：
当前可以选择的数应该是，我们假设是
，那么应该转移到
边界：
, return
,说明枚举完成， 如果,ans++
剪枝：
，无需递归，肯定会越界
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
private static int n;
private static int m;
private static int ans;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
dfs(1,0,0);
System.out.println(ans);
}
private static void dfs(int i,int sum,int pre){
if(sum>n) return;
if(i==m+1){
if(sum==n) ans++;
return;
}
for(int k=pre;k<=n-sum;k++){
if(k*(m-i+1)>n) break;
dfs(i+1,sum+k,k);
}
}
}
查看8道真题和解析