使用单调性优化动态规划.doc

用单调性优化动态规划 【摘要】 单调性作为一类重要的性质，在信息学竞赛中是一种极为的解题突破口，也在动态规划的优化过程中起着至关重要的作用。本文主要选取了几道国内竞赛试题，探讨单调性在动态规划优化中神奇的应用。 【关键字】 单调性 动态规划 队列 凸线 【目录】 【序言】………………………………………………………………………………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必定是的不二人选，因为队列是单调的！ 我们看看怎样将 插入