目录

写在前面：

题目：P1025 [NOIP2001 提高组] 数的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输出格式：

输入样例：

输出样例：

解题思路：

代码：

AC ！！！！！！！！！！

写在最后：

写在前面：

怎么样才能学好一个算法？

我个人认为，系统性的刷题尤为重要，

所以，为了学好深度优先搜索，为了用好暴搜应对蓝桥杯，

事不宜迟，我们即刻开始刷题！

题目：P1025 [NOIP2001 提高组] 数的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

n, k （6 < n ≤ 200，2 ≤ k ≤ 6）

输出格式：

1 个整数，即不同的分法。

输入样例：

7 3

输出样例：

4

提示：

四种分法为：
1, 1, 5;
1, 2, 4;
1, 3, 3;
2, 2, 3.

解题思路：

我们使用深度优先搜索的时候，

第一个要注意的点是搜索的顺序，

因为我们要保证，

我们写出的递归结构能够遍历所有情况。

（以上递归搜索的基本思路，多熟悉总是好的）

 接下来是具体思路：

我们先根据题目条件画出递归搜索树：

根节点：（以题目给出的样例为例）

从第一位置开始，我们从1开始填数字：

题目要求下一个数要大于等于前一个数，

 我们发现，题目要求最大是7，而从3开始最小的和也是9，

我们就能直接判断他是不合法的，需要剪枝。

继续递归搜索：

 我们发现，当1 + 4 + 4 > 7 ， 2 + 3 + 3 > 7，这两个情况之后也需要剪枝，

总结这个剪枝的规律，其实就是：

如果当前的值的总和 + 接下来剩下位置的数量 * 起始数值 > 题目要求的值，

就不用继续递归搜索了。

继续往下递归搜索：

 我们就根据这个规律去实现代码即可：（记得剪枝）

代码：

//包含常用头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;int n, k;//因为题目只需要返回计数，所以不用专门开一个数组记录，直接用一个变量计数即可
int res = 0;void dfs(int u, int start, int sum)
{//遍历完三个位置if(u > k){//如果符合条件if(sum == n)res++;return;}//如果当前的sum + 接下来剩下位置的数量 * 起始数值 > 题目要求的值，就不用继续递归搜索了for(int i = start; sum + i * (k - u + 1) <= n; i++){dfs(u + 1, i, sum + i);}
}int main()
{cin >> n >> k;dfs(1, 1, 0);printf("%d\\n", res);return 0;
}

AC ！！！！！！！！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。