首页 > 其他分享 >折半搜索

折半搜索

时间:2024-04-16 17:44:38浏览次数:26  
标签:折半 int dfs2 dfs1 搜索 发案 代价

折半搜索

折半一般可以把时间复杂度从 \(O(2^{n})\) 变成 \(O(2^{n/2} \cdot n)\)。

一般可以从初始状态搜一次, 从目标状态搜一次。

伪代码

void dfs1(int x, /*其他的状态*/){
	if(x == mid + 1){
		/*
		统计发案数
		*/
	}
	dfs1(x + 1, /*选第 x 个东西的代价*/);
	dfs1(x + 1, /*不选第 x 个东西的代价*/);
}

void dfs2(int x, /*其他的状态*/){
	if(x == mid){
		/*
		统计发案数
		*/
	}
	dfs2(x - 1, /*选第 x 个东西的代价*/);
	dfs2(x - 1, /*不选第 x 个东西的代价*/);
}

dfs1(1, /*...*/);
dfs2(n, /*...*/);

标签:折半,int,dfs2,dfs1,搜索,发案,代价
From: https://www.cnblogs.com/liuyichen0401/p/18138796

相关文章

  • maven-search一款鲁班大叔开发的maven依赖搜索神器
    一款好的插件往往能提高我们的开发效率。今天就给大家安利一款maven依赖搜索插件。插件是自己一直关注的鲁班大叔开发的,用了几天真的好用,废话不多说,我们就来看看这是一款什么插件能干什么?在IDEA中,我们可以使用一些插件来帮助我们更好地管理和搜索Jar包。其中,MavenSea......
  • layUI Table自定义工具栏和搜索参数
    layUITable自定义工具栏和搜索参数视频讲解地址https://www.bilibili.com/video/BV1P94y197nNHTML代码<divclass="container-fluid"><tableclass="layui-hide"id="test"lay-filter="test"></table></div><s......
  • [abc349] [E - Weighted Tic-Tac-Toe ] 搜索
    搜索importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.math.BigInteger;importjava.util.StringTokenizer;publicclassMain{staticlong[][]board=newlong[3][3];staticint[][]chosed=n......
  • SI 2120程序设计图像搜索综合
    工程学院电气学院工程和计算机科学SI2120程序设计范式相似图像搜索综合任务(24%)2024年冬季最多两名学生一组的项目第1部分将于2月16日23:59之前到期第2部分将于3月8日23:59之前到期第3部分和第4部分将于4月22日23:59之前到期延迟分配政策:每延迟一天减10%。例如:一个项目周五晚上......
  • C++算法题解 - 递归实现排列型枚举 - 递归法 (图文) (递归搜索树)
    题目:递归实现排列型枚举把1∼n这n个整数排成一行后随机打乱顺序,输出所有可能的次序。输入格式一个整数n。输出格式按照从小到大的顺序输出所有方案,每行1个。首先,同一行相邻两个数用一个空格隔开。其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。数据......
  • 网易云音乐搜索与播放APP设计
    一、原型工具优缺点对比墨刀、Axure、Mockplus都是常见的原型设计工具,它们在适用领域和优缺点上有着各自的特点:墨刀:适用领域:墨刀适用于快速原型设计和团队协作。它的界面简洁易用,支持多种交互和动画效果,适合用于移动应用和网页的设计。优点:简单易上手,无需编码经验;提供在线协......
  • 数组搜索和位置方法总结(indexOf()、lastIndexOf()、includes()、find()、findIndex())
    1.严格相等(indexOf()、lastIndexOf()、includes())这三个方法都接受两个参数(要查找的元素、可选的起始搜索位置)indexOf()、includes()从数组第一项往后搜索,lastIndexOf()从数组最后一项往前开始搜索indexOf与lastIndexOf返回要查找的元素在数组中的位置,如果没有找到返回-1,incoude......
  • Elastic学习之旅 (9) 结构化搜索
    大家好,我是Edison。上一篇:基于Term和全文的ES查询结构化数据结构化搜索(StructuredSearch)是指对结构化数据的搜索,那么,什么数据是结构化的呢?ES中日期、布尔类型和数字都是结构化的。另外,文本也可以是结构化的:比如彩色笔可以有离散的颜色集合:红、蓝、绿等;一个博客也可能......
  • Avalonia下拉可搜索树(TreeComboBox)
    1.需求分析  树形下拉的功能是ComboBox和TreeView的功能结合起来,再结合数据模板来实现这一功能。2.代码实现 1.创建UserControl集成TreeView控件`publicclassTreeComboBox:TreeView{privatebool_isPushTextChangedEvent=true;privateButtonClearButton;pri......
  • 数据结构之二叉搜索树(java语言版)
    之前介绍了树,主要实现了二叉树的代码。在二叉树的基础上有许多衍生的树,如二叉搜索树、哈夫曼树等,今天学习一下二叉搜索树。二叉搜索树二叉搜索树是二叉树的一种,是应用非常广泛的一种二叉树,英文简称为BST又被称为:二叉查找树、二叉排序树特点任意一个节点的值都大于其左子树所......