傻人题解 | #放苹果#

思路：

本篇题解很适合和我一样不怎么聪明的人，虽然这是简单题，但还是难倒了我。但是这道题数据范围小，我们可以想到暴力来求解。

根据题意，不同顺序的分法记录为一种，所以可以人为的安排一种顺序。这里假设为升序（允许重复）

对于题目的例子，模拟如下：

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);
        }
    }
}