欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷java实现(P1025_数的划分)

程序员文章站 2022-07-13 11:10:01
...

题目链接:https://www.luogu.com.cn/problem/P1025

洛谷java实现(P1025_数的划分)


看题目我们不难发现,典型的深搜+回溯+剪枝;
看实例答案我们可以发现数据特征:

  1. 后面的数要大于等于前一个数,(保证了不重复的分法)
  2. 数据逐渐成均匀分布
  3. 每当确定一个数后面的数可均分剩下的数
public class Main {
    static int n, k, count;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        k = in.nextInt();
        dfs(1, 1, 0);
        System.out.println(count);
    }

    /**
     * @param floor  为第几个数
     * @param before 前一个数
     * @param sum    前面数和
     */
    private static void dfs(int floor, int before, int sum) {
        if (floor == k) {
            count++;
            return;
        }
        int end = (n - sum) / (k + 1 - floor);//总数减去前面分配好的数和,剩下的数平分
        for (int i = before; i <= end; i++) {//下一个数一定大于等于前一个数
            dfs(floor + 1, i, sum + i);
        }
    }
}