当前位置：首页 > news >正文

【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs（5）

news 2025/8/16 3:47:32

写在前面：

题目：P2036 [COCI2008-2009#2] PERKET - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输出格式：

输入样例：

输出样例：

解题思路：

代码：

AC ！！！！！！！！！！

写在最后：

写在前面：

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

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

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

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

题目：P2036 [COCI2008-2009#2] PERKET - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

第一行一个整数 n，表示可供选用的食材种类数。

接下来 n 行，每行 2 个整数 si 和 bi，表示第 i 种食材的酸度和苦度。

输出格式：

一行一个整数，表示可能的总酸度和总苦度的最小绝对差。

输入样例：

输入1：

1
3 10

输入2：

2
3 8
5 8

输入3：

输出样例：

输出1：

输出2：

输出3：

提示：

解题思路：

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

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

因为我们要保证，

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

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

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

接下来是具体思路：

根据题目的要求，

我们能判断出调料的选择方式，

每种调料有两种情况，选或者不选，

我们发现这其实就指数型枚举的思想，

根据这个思路，我们来画一个递归搜索树：

根节点：（以输入2的样例作为例子）

有两行共四种调料：

每种有选和不选的情况：

但是题目有一个要求就是必须要选择一种调料，

如果最后有情况是全部没选的，那就要剪枝，

再继续往下递归：

因为选过的数就不能再选了，

我们可以定义一个变量，每次初始化成false ，

如果该位置有调料就为true ，否则就是false。

递归的时候就直接：

定义一个数组来记录，如果选过就是1，没选是0，不选是2。

那么废话不多说，我们来看代码：

代码：

//包常用头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;int n;//因为要求出最小值，所以先定义一个很大的数
int res = 1e9;
const int N = 20;//记录酸和苦
int scid[20], bitter[20];
int st[N];void dfs(int u)
{//每次进来都初始化成falsebool has = false;if(u > n){int sum1 = 1;int sum2 = 0;for(int i = 1; i <= n; i++){if(st[i] == 1){//如果选了调料就truehas = true;sum1 *= scid[i];sum2 += bitter[i]; }}//如果选了调料才计算if(has)res = min(res, abs(sum1 - sum2));return;}//选了st[u] = 1;dfs(u + 1);st[u] = 0;//不选st[u] = 2;dfs(u + 1);st[u] = 0;}int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d %d", &scid[i], &bitter[i]);}dfs(1);printf("%d\n", res);return 0;
}