Tyvj2018 小猫爬山 - 搜索 - 剪枝/迭代加深_小猫爬山 迭代加深-程序员宅基地

技术标签: 搜索  暴力  NOIP  

学习OI很久以后才发觉自己对于搜索的认识有极大的偏差。。。
因为没有好好寻找一些算法资料。。。在学习时把枚举和搜索混为一谈,而且一直认为搜索就是全排列,导致我数次打出指数复杂度的暴力-_-
整理资料后才发现,指数型枚举有组合与排列,而搜索和枚举其实有很大的差别,枚举只是属于搜索的一丢丢最暴力的部分而已


  • 枚举,直接一个个找,一般在枚举的方式上优化,使得枚举更加方便,也更容易找到答案(比如说状态压缩,直接枚举数字,比直接枚举各种状态方便了不少)
  • 搜索的内核和DP大体上是一致的。首先根据题意设置出状态,然后寻找到阶段,思考在某一个阶段能够发展出多少分支,分支又会怎样改变状态,遍历所有分支找到最优解。有时需要开一些数据结构记录状态

对于这道题,状态是小猫坐缆车的具体方案,阶段是目前安排了几只小猫(我们需要一步步确定最终解,而不是一次把解求出来,所以要这样划分阶段),分支有两种,小猫可以选择一个还坐的下的缆车,或者再租一辆缆车。用一个数组记录“具体方案”:设cab[i]表示第i辆缆车已经承受的重量。

但是这样很慢。。。我们至多租n辆缆车,又有n只小猫要安排,复杂度在 n

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Fantasy_World/article/details/80924676

智能推荐

04-Foundation-NSSet、NSDictionary、block-程序员宅基地

文章浏览阅读117次。目录:一、NSSet集合二、NSDictionary字典三、block代码块回到顶部一、NSSet集合1 NSSet是一个无序的,管理对个对象的集合类,最大特点是集合中不允许出现重复对象,和数学上的集合含义是一样的。除了无序,不许重复,其他功能和NSArray是一样的。2 什么叫重复?* 同一个对象* 两个对象信息值一样计算机认为的一样是:..._nsdictionary block

Swift编程十七(可选链接)_swift 文件公开链接-程序员宅基地

文章浏览阅读247次。案例代码下载可选链接可选链接是一个查询和调用当前可能为nil的可选项的属性,方法和下标的过程。如果optional包含值,则属性,方法或下标调用成功; 如果optional是nil,则属性,方法或下标调用返回nil。多个查询可以链接在一起,如果链中的任何链接为nil,则整个链都会正常失败。注意: Swift中的可选链接类似于Objective-C中的nil消息传递,但其方式适用于任何类型,..._swift 文件公开链接

OpenSSL之ssl库_ssl_read_ex-程序员宅基地

文章浏览阅读4.6k次。sslOpenSSL的SSL/TLS库,实现了SSL(Secur)/TLS(Transport Layer Security)/DTLS(Datagram Transport Layer Security)协议的多个版本。SSL_CTX对象包含证书、算法等信息,用于建立TLS/SSL连接。网络连接建立后可以赋值给SSL对象,然后可以使用SSL对象完成握手操作(SSL_accept或SSL_connect或SSL_do_handshake),握手完成后就可以读写了。关闭网络连接前先调用SSL_shutd_ssl_read_ex

285、基于51单片机的电子秤称重超重报警系统设计(程序+原理图+PCB图+参考论文+开题报告+设计资料+制作详解+程序流程图+元器件清单等)_超重报警电子秤总体设计方案-程序员宅基地

文章浏览阅读809次。方案一:AT89C52是美国ATMEL公司生产的低电压,高性能CMOS型8位单片机,器件采用ATMEL公司的高密度、非易失性存储技术生产,兼容标准MCS-51指令系统,片内置通用8位中央处理器(CPU)和Flash存储单元,功能强大。其片内的8K程序存储器是FLASH工艺的,这种单片机对开发设备的要求很低,开发时间也大大缩短。写入单片机内的程序还可以进行加密,这又很好地保护我们的劳动成果。再者,AT89C52目前的售价比8031还低,市场供应也很充足。_超重报警电子秤总体设计方案

c语言编程题及答案汇总,c语言编程题及答案-程序员宅基地

文章浏览阅读248次。资源描述:C C 语言编程题及答案(三)语言编程题及答案(三) 1. 给小学生出加法考试题 编写一个程序,给学生出一道加法运算题,然后判断学生输入的答案对错与否,按下列 要求以循序渐进的方式编程。 程程序序 1 通过输入两个加数给学生出一道加法运算题,如果输入答案正确,则显示 “Right” , 否则显示“Not correct Try again” ,程序结束。 程程序序 2 通过输入两个加数给..._1)通过输入两个加数给学生出一道加法运算题,如果输入答案正确,则显示“right!”,

给定一个只包含小写字母的字符串,删除重复的字母,每个字母只出现一次。在所有结果中,输出字典顺序最小的。_给定一个仅包含小写字母的字符串,去除字符串中重复的字母,使得每个字母只出现一次-程序员宅基地

文章浏览阅读1.6w次,点赞5次,收藏6次。本题源自leetcode 316---------------------------------------------------------------------------------思路:1 用俩个vector 标记字符在串中的出现的次数,以及这个字符是否访问过。 2 先遍历一遍字符串,统计字符出现的次数3 第二遍遍历字符,每次访问一个字符都将字符出现的次数减一,如_给定一个仅包含小写字母的字符串,去除字符串中重复的字母,使得每个字母只出现一次

随便推点

基于博图TIA中SCL语言编写CRC校验功能块_博图crc校验程序-程序员宅基地

文章浏览阅读574次,点赞5次,收藏3次。在这里直接体现源码,感兴趣的可以提出修改建议,以及自己的一些想法。_博图crc校验程序

POE介绍-程序员宅基地

文章浏览阅读317次。POE是"Power over Ethernet"的缩写,它是一种通过以太网(Ethernet)网络传输电力的技术。POE的标准规定了不同供电能力的级别,从而适应不同设备的功耗需求。IEEE 802.3af(POE)提供最高15.4瓦的功率,而IEEE 802.3at(POE+)则提供最高30瓦的功率。POE技术的应用使得网络设备的安装和维护更加便利,特别是在需要灵活布置设备的情况下。有一些设备可以作为POE中继器,允许将POE信号传输到更远的距离,从而扩大了POE的应用范围。

信息系统项目管理师(2022年) —— 第 3 章 项目立项管理_论信息系统项目的立项管理-程序员宅基地

文章浏览阅读2.3k次。1、立项内容管理项目立项一般包括提交项目建议书、项目可行性研究、项目招标与投标等内容。1.1 项目建议书项目建议书(又称立项申请)是项目建设单位向上级主管部门提交项目申请时所必须的文件,是该项目建设筹建单位或项目法人,提出的某一具体项目的建议文件,是对拟建项目提出的框架性的总体设想。项目建议书是项目发展周期的初始阶段,也是可行性研究的依据,在项目建议书批准后,方可开展对外工作。1.1.1 项目建议书内容(1)项目的必要性。(2)项目的市场预测。(3)产品方案或服务的市场预测。(4)项_论信息系统项目的立项管理

【转】android获取所有安装的非系统应用_app读取应用列表怎么区分是否系统应用-程序员宅基地

文章浏览阅读5.3k次,点赞2次,收藏3次。程序大概分成三个部分:1.获取手机已安装的所有应用package的信息(其中包括用户自己安装的,还有系统自带的);2.滤除系统自带应用;3.通过列表显示出应用程序的图标(icon),和其他文字信息(应用名称,包名称package name,版本号等等)首先,我们定义一个数据结构,来保存应用程序信息(icon,name,packageName,versionName,_app读取应用列表怎么区分是否系统应用

wamp集成环境自己的项目访问时出现地址栏自动去掉localhost的问题-程序员宅基地

文章浏览阅读95次。这是在www目录下的index.php文件有参数没有设置好。然后修改里面查找$projectContents,或直接查看338行代码,修改'http://'为'http://localhost/'即可(再试应该就可以了) ..._php a herf 链接跳转外部页面 去掉开头的 localhost 目录信息

图象工具:可将SWING组件外观输出成图片的工具 - SWING组件_swing打印出组件的图片-程序员宅基地

文章浏览阅读1.8k次。图象工具:可将SWING组件外观输出成图片的工具---------------------------------------- 我的自定义SWING组件 !!! 王 晋 (Edward W.J.)Email:[email protected]:(0)13482058688_swing打印出组件的图片

推荐文章

热门文章

相关标签