建站到网站收录到优化,各网站的网络联盟,wordpress登录页面修改,怎么怎么做网站目录
写在前面#xff1a;
题目#xff1a;P2036 [COCI2008-2009#2] PERKET - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述#xff1a;
输入格式#xff1a;
输出格式#xff1a;
输入样例#xff1a;
输出样例#xff1a;
解题思路#xff1a;
代码…目录
写在前面
题目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
4
1 7
2 6
3 8
4 9
输出样例
输出1
7
输出2
1
输出3
1
提示
解题思路
我们使用深度优先搜索的时候
第一个要注意的点是搜索的顺序
因为我们要保证
我们写出的递归结构能够遍历所有情况
在我们初学搜索的时候我们一定要画一个递归搜索树观察
递归非常抽象画图能很好的帮助我们解题。以上递归搜索的基本思路多熟悉总是好的 接下来是具体思路
根据题目的要求
我们能判断出调料的选择方式
每种调料有两种情况选或者不选
我们发现这其实就指数型枚举的思想
根据这个思路我们来画一个递归搜索树
根节点以输入2的样例作为例子 有两行共四种调料 每种有选和不选的情况 但是题目有一个要求就是必须要选择一种调料
如果最后有情况是全部没选的那就要剪枝 再继续往下递归 因为选过的数就不能再选了
我们可以定义一个变量每次初始化成false
如果该位置有调料就为true 否则就是false。
递归的时候就直接
定义一个数组来记录如果选过就是1没选是0不选是2。 那么废话不多说我们来看代码
代码
//包常用头文件
#include cstdio
#include cstring
#include iostream
#include algorithmusing 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;
}AC 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。
