【转】单调队列优化DP
2024-04-02 16:54:26
转自 : http://www.cnblogs.com/ka200812/archive/2012/07/11/2585950.html
单调队列是一种严格单调的队列,可以单调递增,也可以单调递减。队首位置保存的是最优解,第二个位置保存的是次优解,ect。。。
单调队列可以有两个操作:
1、插入一个新的元素,该元素从队尾开始向队首进行搜索,找到合适的位置插入之,如果该位置原本有元素,则替换它。
2、在过程中从队首删除不符合当前要求的元素。
单调队列实现起来可简单,可复杂。简单的一个数组,一个head,一个tail指针就搞定。复杂的用双向链表实现。
用处:
1、保存最优解,次优解,ect。
2、利用单调队列对dp方程进行优化,可将O(n)复杂度降至O(1)。也就是说,将原本会超时的N维dp降优化至N-1维,以求通过。这也是我想记录的重点
是不是任何DP都可以利用单调队列进行优化呢?答案是否定的。
记住!只有形如 dp[i]=max/min (f[k]) + g[i] (k<i && g[i]是与k无关的变量)才能用到单调队列进行优化。
优化的对象就是f[k]。
最新文章
- 【从零开始学BPM,Day2】默认表单开发
- PyQt5+Python3.5.2-32bit开发环境搭建
- 早安Visual Studio!一次重构之旅,夏洛特烦恼
- 一款经典的jQuery kxbdMarquee 无缝滚动插件
- 模仿QQ左滑删除
- atitit.二维码生成总结java zxing
- codeblocks 配置交叉编译和调试环境
- jquery 过滤器
- 强大的微软Microsoft Translator翻译接口
- error C2018: unknown character &#39;0xa1&#39;
- Spring基于 Annotation 的简单介绍
- SQL Server 优化存储过程的七种方法
- storage size of &#39;xxx&#39; isn&#39;t known问题出现的可能原因之一
- C# 处理文件的压缩与解压
- MySQL数据库优化小建议
- Madgwick IMU Filter
- SQL语句操作优先级顺序
- nginx的一些基本功能
- 查看Linux下系统资源占用常用命令
- C# 程序运行中的流程控制