目录

写在前面：

题目：P2089 烤鸡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输出格式：

输入样例：

输出样例：

提示：

解题思路：

代码：

AC ！！！！！！！！！！

写在最后：

写在前面：

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

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

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

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

题目：P2089 烤鸡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

一个正整数 n，表示美味程度。

输出格式：

第一行，方案总数。

第二行至结束，10 个数，表示每种配料所放的质量，按字典序排列。

如果没有符合要求的方法，就只要在第一行输出一个 0。

输入样例：

11

输出样例：

10
1 1 1 1 1 1 1 1 1 2 
1 1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 2 1 1 1 
1 1 1 1 1 2 1 1 1 1 
1 1 1 1 2 1 1 1 1 1 
1 1 1 2 1 1 1 1 1 1 
1 1 2 1 1 1 1 1 1 1 
1 2 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1 

提示：

对于 100% 的数据，n ≤ 5000。

解题思路：

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

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

因为我们要保证，

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

在我们初学搜索的时候，我们一定要画一个递归搜索树观察，

递归非常抽象，画图能很好的帮助我们解题。（以上递归搜索的基本思路，多熟悉总是好的）

 接下来是具体思路：

我们之前练习了三道模板题，dfs的题目的思路大多是他们的变式：

1. 指数级枚举

2. 排列型枚举

3. 组合型枚举

我们可以从这三个角度思考这道题目，

我们一共使用10种调料，

而每种调料有三种选择，1、2、3克，这其实与指数级枚举类似，

让我们来画一下递归搜索树：

根节点：（我们就那一种情况举例画图）

 它有三种选择可以往下递归搜索：

然后第二个数也有三种选择：

 第三个数也有三种选择：

 以此类推，就能搜索出所有的情况了。

 下面是代码实现：

代码：

//包常用头文件
#include 
#include 
#include 
#include #include using namespace std;//根据题目开大小
const int N = 20;int n;//需要返回的情况数量
int ret = 0;//记录数据
int arr[N];//用二维数组存需要输出的值
vector> res;void dfs(int u, int sum)
{//如果总和已经比n大，直接返回（剪枝）if(sum > n)return;if(u > 10){//如果符合要求就存进数组if(sum == n){vector v;ret++;for(int i = 1; i <= 10; i++){v.push_back(arr[i]);}res.push_back(v);}return;}//搜索for(int i = 1; i <= 3; i++){arr[u] = i;//记录数据dfs(u + 1, sum + i);arr[u] = 0;//恢复现场}
}int main()
{scanf("%d", &n);dfs(1, 0);printf("%d\n", ret);//输出for(int i = 0; i < ret; i++){for(int j = 0; j < 10; j++){printf("%d ", res[i][j]);}puts("");}return 0;
}

AC ！！！！！！！！！！

写在最后：

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

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

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

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