洛谷java实现(P1025_数的划分)
程序员文章站
2022-07-13 11:10:01
...
看题目我们不难发现,典型的深搜+回溯+剪枝;
看实例答案我们可以发现数据特征:
- 后面的数要大于等于前一个数,(保证了不重复的分法)
- 数据逐渐成均匀分布
- 每当确定一个数后面的数可均分剩下的数
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);
}
}
}
下一篇: HDU 1698 Just a Hook