- 1、本文档共19页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
用单调性优化动态规划
【摘要】
单调性作为一类重要的性质,在信息学竞赛中是一种极为的解题突破口,也在动态规划的优化过程中起着至关重要的作用。本文主要选取了几道国内竞赛试题,探讨单调性在动态规划优化中神奇的应用。
【关键字】
单调性 动态规划 队列 凸线
【目录】
【序言】………………………………………………………………………………3
【正文】……………………………………………………………….………………4
一.什么是单调队列…………………………………..…………………………...4
1.单调队列的性质………………………………………………….………..5
2.单调队列有什么用………………………………………………………...5
3.时间效率分析……………………………………………………………...5
4.为什么这样做……………………………………………………………...5
5.一些总结……………………………………………………………….…..6
二.一些简单的例子…………………………………………………………….…7
【例一】生产产品Vijos1243………………………………………….………7
题目描述…………………………………………………………………7
解法分析…………………………………………………………………7
【例二】Cut the Sequence——Pku3017………………….………………….8
题目描述……………………………………………………………........8
解法分析…………………………………………………………………8
小结……………………………………………………………................9
三.一些更复杂的例子…………………………………………………………..10
【例三】Toy HNOI08….…………………………………………..………..10
题目描述………………………………………………………………10
朴素的解法……………………………………………………………10
正确的解法……………………………………………………………10
为什么决策单调?……………………………………………………11
【例四】Storage Zjtsc07……………………………………….………..….12
题目描述………………………………………………………………12
解法分析………………………………………………………………12
四.利用凸线的单调性来优化Dp……………………………………………….15
【例五】货币兑换NOI2007………………………………………………..15
题目描述………………………………………………………………15
解法分析………………………………………………………………15
【全文总结】
【参考文献】
【感谢】
【正文】
什么是单调(双端)队列
单调队列,顾名思义,就是一个元素单调的队列,那么就能保证队首的元素是最小(最大)的,从而满足动态规划的最优性问题的需求。
单调队列,又名双端队列。双端队列,就是说它不同于一般的队列只能在队首删除、队尾插入,它能够在队首、队尾同时进行删除。
【单调队列的性质】
一般,在动态规划的过程中,单调队列中每个元素一般存储的是两个值:
在原数列中的位置(下标)
他在动态规划中的状态值
而单调队列则保证这两个值同时单调。
【单调队列有什么用】
我们来看这样一个问题:一个含有n项的数列(n=2000000),求出每一项前面的第m个数到它这个区间内的最小值。
这道题目,我们很容易想到线段树、或者st算法之类的RMQ问题的解法。但庞大的数据范围让这些对数级的算法没有生存的空间。我们先尝试用动态规划的方法。用代表第个数对应的答案,表示第个数,很容易写出状态转移方程:
这个方程,直接求解的复杂度是O(nm)的,甚至比线段树还差。这时候,单调队列就发挥了他的作用:
我们维护这样一个队列:队列中的每个元素有两个域{position,value},分别代表他在原队列中的位置和,我们随时保持这个队列中的元素两个域都单调递增。
那计算的时候,只要在队首不断删除,直到队首的position大于等于,那此时队首的value必定是的不二人选,因为队列是单调的!
我们看看怎样将 插入
您可能关注的文档
- WINCC.V7.3安装教程介绍.doc
- 12年全国各地中考物理试题压强和浮力汇编(含答案).doc
- 机械液性塑料聚合物心轴夹具设计及分析.doc
- 空气动理论力学111.doc
- L4S5M计算机主板指导书.doc
- AutOCAD自学教材.doc
- 网店总结总结报告.doc
- 工程力学练习题答案9廖明成.doc
- 电力电工实训手册1.doc
- EPSONME1100L13001800字车感应传感器安装图解.docx
- 《GB/Z 44363-2024致热性 医疗器械热原试验的原理和方法》.pdf
- GB/T 16716.6-2024包装与环境 第6部分:有机循环.pdf
- 中国国家标准 GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统.pdf
- 《GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统》.pdf
- GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统.pdf
- 中国国家标准 GB/T 44315-2024科技馆展品设计通用要求.pdf
- GB/T 44305.2-2024塑料 增塑聚氯乙烯(PVC-P)模塑和挤塑材料 第2部分:试样制备和性能测定.pdf
- 《GB/T 44315-2024科技馆展品设计通用要求》.pdf
- GB/T 44315-2024科技馆展品设计通用要求.pdf
- GB/T 39560.9-2024电子电气产品中某些物质的测定 第9 部分:气相色谱-质谱法(GC-MS)测定聚合物中的六溴环十二烷.pdf
文档评论(0)