[数据结构与算法]洛谷题解P1025&计蒜客题解T2155-【NOIP2001提高组】数的划分

题目概况

计蒜客链接： https://nanti.jisuanke.com/t/T2155
洛谷链接： https://www.luogu.com.cn/problem/P1025
题目难度： 普及/提高-（计蒜客评级普及T3）

题目分析

简化题目： 题目简洁明了
涉及知识点： 深度优先搜索及剪枝策略
解题思路： 其实大体上就是普通的深搜，我们设cnt为当前划分份数， sum为当前累和，last为上一个被选择的数。但是200的数据量对于dfs来说还是有点大，我们必须从上一个被选择的数循环到sum+i*(k-cut)<=n。（循环范围的界限意思是当前累和加上剩余份都是i的总和）

代码拆解与要点分析

代码比较简短，你们可以直接看完整版的注释

完整代码

#include <iostream>
#include <cstdio>

using namespace std;

int n, k, ans; //按照题目设定；ans为方案数

void dfs(int last, int sum, int cnt) {
	if (cnt == k) {
		if (sum == n) {
			ans++;
		}
		return; //注意，这个return只要你选到了k份你就得回溯；要不然继续划分k+份那还得了
	} 
	for (int i = last;sum+i*(k - cnt)<= n;i++) {//循环范围！！！
		dfs(i, sum + i, cnt + 1);
	}
	return; 
}
int main() {
	cin >> n >> k;

	dfs(1, 0, 0);

	cout << ans << endl;
	return 0;
}