P1025 [NOIP2001 提高组] 数的划分

知识点：深搜，剪枝

难度：3

这个是深搜剪枝的入门题，难度较低但是比较适合入门的，题目问的是有多少方案，那么我们统计方案的时候一定要让数字是单调不增或者单调不减的，不然的话会出现重复的情况，因为是统计种类数，那么从小到大从大到小都可以，下面是从小到大的搜索，我们记录每一层选的数是什么，然后我们选下一层的数的上下界要选对，下界就是上一层的数，上界就是我们还可以选的数字和除以没有选的数字的个数，

接下来是一个比较重要的剪枝，我们走到第k个数的时候，如果我们剩下的指标，也就是选数的空间，大于等于第k-1个数的时候，这个时候不需要继续往下走了，这个时候可以答案加一，相当于已经找到了答案，我之前还是要把所有的数都选出来，要走到第k+1层，现在想想是真的多余，因为已经走打了第k个数，那么它的选择其实就只有那一个了，剩余的遍历只有一个是有效的，其余的都是多余的，我写的那个剪枝也没有用上，也就是剩余的数都选最小的最后也会比n大，那么就剪枝掉，现在想想这个从小到大的搜索比从大到小的搜索要好，因为一旦想出它的上下界，那么它的上下界是比你从大到小要紧凑的，

还有，这个题从小到大搜是比从大到小搜要快的，可以思考一下为什么会这样

#include 
 
using namespace std;
 
int n, c, rec[10], ans;
 
void dfs(int k, int sum) {
	if (sum + rec[k - 1] * (c - k + 1) > n) return;
	if (k == c) {
		if (n - sum >= rec[k - 1]) ans++;
		return;
	}
	for (int i = rec[k - 1]; i <= (n - sum) / (c - k + 1); i++) {
		rec[k] = i;
		dfs(k + 1, sum + i);
	}
}
 
int main() {
	cin >> n >> c;
	rec[0] = 1;
	dfs(1, 0);
	cout << ans;
	return 0;
}