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

洛谷P1025 Java解法

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

题目出处
洛谷P1025 Java解法
思路:DFS,开一个数组arr[]存储每次满足条件的k个值,每当数组满了且数组里所有数的和等于n时就分法++,不过如果单纯这样暴力搜肯定会TLE,因此我们注意到每一次存入数组里的数必须大于等于前一个数,所以我们设置一个变量zz每次存储当前数,以后每一次从zz开始搜即可。但是我们发现这样还是会TLE,因为我们只确定了每一次存入数组大的下限,而没有规定上限,注意到总和必须为n,因此我们每次搜到的数肯定不能大于n减去前面已经搜过的数的和,这样一来就完成了基础的剪枝。

代码十分易懂:

package search;

import java.util.Arrays;
import java.util.Scanner;

public class P1025 {

	static int arr[], num, n, k;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		arr = new int[k];
		dfs(0, 0, 1);
		System.out.println(num);
//		System.out.println(Arrays.toString(arr));
	}

	public static void dfs(int index, int sum, int zz) {
		if (sum == n && index == k) {
//			System.out.println(Arrays.toString(arr));
			num++;
			return;
		}
		if (sum > n || index >= k) {
			return;
		}
//		if (sum > (index + 1) * n / k) {
//			return;
//		}
		for (int i = zz; i <= n - sum; i++) {
			arr[index] = i;
			dfs(index + 1, sum + i, i);
		}
	}
}