搜索Ex (洛谷提高历练地)
2024-10-19 04:03:45
搜索Ex
P1120 小木棍
题意:不超过65根长度小于50的小木棍(是由一批等长木棍砍断得到的),求原始木棍的最小可能长度
分析:优化+减枝爆搜
搜索状态要记录当前尝试的已经填好的长度,当前尝试填的木棍的id,以及已经填好了的木棍的数量。
- 优先考虑长度大的木棍,因为组合原始木棍时,长的适应性比较差
- 在组合之后的一个木棍中,组成它的小木棍顺序如果不做要求,会导致重复搜索很多状态,所以可以规定先后加入一根原始木棒的木棍长度时递减的。
- 记录最近一次搜索过的木棍长度,接下来跳过与他等长的木棍
- 对于一个新尝试的原始木棍,如果一开始插入的就是失败的,那么当前分支直接返回失败
- 对于刚拼凑好的一个原始木棍,如果递归分支返回失败,那么当前分支也会失败。
P1378 油滴扩展
分析:\(N \le 6\),所有情况 \(6! = 720\) 种,对于每种顺序,从1到n依次考虑当前油滴能够扩展的最大半径,最后用长方形面积减去即可
P1514 引水入城
分析:首先要想到的一个是对于每个可以建设蓄水厂的位置,它能所及的邻近沙漠的城市是有一个范围的,另外通过样例可以注意到水可以往上走,所以这题如果按照从下向上DP求范围是不对的,能够想到的办法就是记忆化了,求出区间范围之后就是一个最小区间覆盖的问题,直接贪心求或者DP求都是可以的。
P1312 Mayan游戏
这题还没写,之后补
P1441 砝码称重
分析:很容易可以想到是用背包求,n个砝码去掉m个共$C_n^m$种,每个砝码最重100,所以就是一个$(n-m)^2*100$ 复杂度的背包。
P1242 新汉诺塔
分析:原来的汉诺塔一开始只会在一个柱子上,比如在A,最终要把所有的移动到C,我们要先把除了最大的其他所有的移动到B,再把最大的移动到C,这样做是保证最优的。但是在此题中就不灵验了,因为当前最大的那个圆盘或许可以直接到达目标柱,这是因为比他小的都在第三个柱子上。可以想到这个情况只会在一开始调整最大圆盘时发生,这是因为调整它之后,其他所有盘都在一个柱子上,问题就会变成原始的汉诺塔问题了。
最新文章
- HttpUrlConnection
- 那些年,我们在Django web开发中踩过的坑(一)——神奇的‘/’与ajax+iframe上传
- Finding Nemo_BFS
- RMAN_学习实验1_RMAN备份标准过程(案例)
- 动态链接库dll的 静态加载 与 动态加载
- 西门子PLC学习笔记七-(位逻辑指令)
- 一个简单的使用restc demo
- spring 集成mongo配置
- 规范 : Sql statusEnum
- 基于百度地图SDK和Elasticsearch GEO查询的地理围栏分析系统(1)
- Uva - 1598 - Exchange
- Python函数式编程之lambda表达式
- 基于JavaCv并发读取本地视频流并提取每帧32位dhash特征
- html知识点汇总(持续更新中)
- 采用Google预训bert实现中文NER任务
- JS—ajax及async和defer的区别
- idea快捷键列表
- Hadoop 系列文章(一) Hadoop 的安装,以及 Standalone Operation 的启动模式测试
- js保留两位小数方法总结
- notion笔记
热门文章
- python Logger模块单例模式
- Spring Boot Security 国际化 多语言 i18n 趟过巨坑
- 【Flutter】容器类组件之填充
- 2021升级版微服务教程7-OpenFeign实战开发和参数调优
- 【RAC】运行root.sh的时候报错root.sh Oracle CRS stack is already configured and will be running under init(1M)
- ctfhub技能树—web前置技能—http协议—Cookie
- Redis 实战 —— 01. Redis 数据结构简介
- 安装jdk-windows系统
- Spring Cloud Alibaba学习笔记
- 3、wait和waitpid