《用单调性优化动态规划》由会员分享，可在线阅读，更多相关《用单调性优化动态规划（19页珍藏版）》请在金锄头文库上搜索。
1、JSOI2009 集训队论文 - 1 -用单调性优化动态规划【摘要】单调性作为一类重要的性质，在信息学竞赛中是一种极为常见的解题突破口，也在动态规划的优化过程中起着至关重要的作用。本文主要选取了几道国内竞赛试题，探讨单调性在动态规划优化中神奇的应用。【关键字】单调性 动态规划 队列 凸线 JSOI2009 集训队论文 - 2 -【目录】【序言】.3【正文】.4一什么是单调队列.41.单调队列的性质.52.单调队列有什么用.53.时间效率分析.54.为什么这样做.55.一些总结.6二一些简单的例子.7【例一】生产产品Vijos1243.7 题目描述7解法分析7【 例二】Cut the Seque
2、ncePku3017.8题目描述.8JSOI2009 集训队论文 - 3 -解法分析8小结.9三一些更复杂的例子.10【例三】Toy HNOI08.10题目描述10朴素的解法10正确的解法10为什么决策单调？11【例四】Storage Zjtsc07.12题目描述12解法分析12四利用凸线的单调性来优化Dp.15【例五】货币兑换NOI2007.15题目描述15解法分析15【全文总结】【参考文献】【感谢】JSOI2009 集训队论文 - 4 -【正文】一 什么是单调（双端）队列单调队列，顾名思义，就是一个元素单调的队列，那么就能保证队首的元素是最小（最大）的，从而满足动态规划的最优性问题的需求。
3、单调队列，又名双端队列。双端队列，就是说它不同于一般的队列只能在队首删除、队尾插入，它能够在队首、队尾同时进行删除。【单调队列的性质】一般，在动态规划的过程中，单调队列中每个元素一般存储的是两个值：1. 在原数列中的位置（下标）2. 他在动态规划中的状态值JSOI2009 集训队论文 - 5 -而单调队列则保证这两个值同时单调。【单调队列有什么用】我们来看这样一个问题：一个含有 n 项的数列(nj。sumx,y表示产品 1),(,1 jksumjispkfMinjiflk 到 x 在 y 机器上生产所需的时间和。这样的算法时间复杂度是 ，很)*(2lmnO明显不能在时限内完成，需要进行优化。我
4、们由于 j 的取值范围十分小：1j 。我们将其1,),(sumipkfMin进行稍微的变形： ，可以发现括号内的1, isif式子是根据 k 所确定的一个常量，直接对应上文的单调队列的方法，省掉了枚举决策的一维，时间复杂度降为 。)*(2mnO1 选自 Vijos 1243【例二】Cut the sequence2问题描述给定一个有 n 个非负整数的数列 a，要求将其划分为若干个部分，使得每部分的和不超过给定的常数 m，并且所有部分的最大值的和 最小。其中 n=vt+1 Do t t+1，这段代码充分应用了 决策单调的性质。3）当前状态计算完毕，看怎么插入当前状态所对应的二元组。当前状态的二元
5、组必然是凸包上的点，我们用 Graham 的维护方式，不断弹栈（注意维护下凸型 Graham 的方向） ，最后再插入。注意如果决策指针也被弹栈了，那么决策指针应当指向当前状态（决策单调！） 。时间复杂度分析主过程里有一重循环，复杂度为 O(n)。重要的是 while 那段。前面说过，决策指针单调右移，所以 while 总共加起来也是 O(n)，又由于每个点最多出栈一次、进栈一次，所以最后的时间复杂度是 O(n)，我们很顺利的解决了这道题。【利用凸线的单调性优化 Dp】其实，例四是利用一次函数、坐标的单调性来进行算法的优化，已经利用了凸包（其实例三也可以）的优美性质在线性时间解决了问题。 但是，
6、例四中通过代数恒等式变形所得到的线性规划式满足：随着计算状态的逐步推进，JSOI2009 集训队论文 - 16 -直线的斜率单调变化、同时 x 或者 y 也单调变化。如果这两者其中一个不满足条件那该怎么办呢？【例五】货币兑换 Cash5问题描述小 Y 要在 n 天里，进行一次股票的交易，股票有 A 类劵和 B 类劵两种。告诉你每天 A 股票的单价 Ai，B 股票的单价 Bi，以及买入股票的时候得到的A 股票和 B 股票的比率 Ratei。刚开始他手里有 S 元钱，他每天可以有三种操作：买入操作，即将 S 元钱 全部用来买股票，将得到一些 A 股票和 B 股票，其中A 股票数量/B 股票数量=R
7、ate。卖出操作，即将手中的股票全部卖出，得到当天应得的钱数。什么都不干。 求：这 n 天下来最多能赚多少钱？n=10 5解法分析这道题目，其实朴素的解法也十分简单。我们用 f(i)代表第 i 天最后最多能得到多少钱，并且第 i 天要做出卖出操作。当状态 f(i)被计算完之后，我们用 x(i)，y(i)代表将 f(i)这么多钱卖出能得到的 A劵和 B 劵的数量，这个可以通过解方程得出。那么很容易得到状态转移方程：，最后的答案=*)(10jyibjxiaMifij )0,(nifMax5 选自 NOI2007这个方程直接求解时间复杂度依然是 O(n2)的。但这个方程是一个求最值的问题：G=ax
8、+by 。bGay这和例四的方程十分相似，可是 单调么？xi 随着 i 单调么？答案都是ba否定的，我们要另寻他法。JSOI2009 集训队论文 - 17 -但是有一点是要肯定的：最优决策点依然在凸包上。但是查找最优决策点、插入毫无规律。我们先来看怎样查找最优决策点：首先，要维护一个上凸的凸包（因为要求最大值） ，我们观察下面一幅图（加粗的直线代表当前状态对应的直线，其斜率 k=）：ba我们看到，如果一个点成为了最优决策点的话，那么设它左边凸包上的点和它的线段的斜率为 k1，右边的点和它连的线段的斜率为 k2，那么必然有k2=k=k1（我们可以设最左边的点的 k1= ，最右边的点的 k2 设为
9、 ） 。根据这个单调性，查找最优决策就可以用二分查找来在 O(logn)的时间内完成。我们再来看怎样插入一个点。因为要维护凸包，所以先二分查找到在数组中应该插入的位置，然后对两边进行 Graham 式凸包维护。这时候问题来了：怎样删除结点？Move？对，用 Move 是最折中的方法，对于本题来说，有人试过因为数据的原因，Move 可以搞定。但如果要让时间复杂度严格的为 O(nlogn)，得需要平衡树。下面是这道题的算法步骤：1）建立一颗以横坐标为关键字的平衡树（本文以 Splay 为例） 。2）二分查找最优决策点，计算状态值。3）插入节点：将该节点的横坐标 a 插入 Splay。接下来，要对左
10、边和右边进行凸线的维护。我们以左边为例（右边类似）：首先再二分查找出离当前点最JSOI2009 集训队论文 - 18 -近的，并且满足凸包性质（因为是上凸形，所以斜率单调减）的点 b。然后根据 graham 的特点：被删掉的点一定是连续的一段，我们可以将点 b 伸展到根节点，a 伸展到跟的右子树，那么 a 的右子树肯定是要被删的点，直接将其删除。但要注意的一点是：a 不一定是凸包上的点，所以向左、向右弄完之后还要检查 a 是否符合凸包要求，不行的话依然要删掉。这样，这道难题就被我们在对数级的时间内完成了。【全文总结】本文通过 5 个经典的例题，阐述了单调性在动态规划试题中的应用。5 个例题各具
11、特色，各有自己的代表性，难度可以说由浅入深。希望读者能够认真阅读，体会其中的奥妙。在许多问题里，单调性是打开胜利之门的钥匙，是指引胜利彼岸的灯塔，是飞上成功蓝天的翅膀，是浇灌成功之花的甘露。【参考文献】1）1D1D 动态规划优化初步 作者：南京师范大学附属中学 汪一宁2）2007 中国信息学奥林匹克年鉴 主编：中国计算机学会JSOI2009 集训队论文 - 19 -3）算法艺术与信息学竞赛主编：刘汝佳&黄亮4）凸完全单调性的一个加强与应用中国国家集训队论文 2007 作者：杨哲5）浅谈基于分层思想的网络流算法中国国家集训队论文 2007 作者：王欣上【感谢】感谢南师附中的汪一宁同学一直以来对我的帮助感谢浙江省绍兴市第一中学的董华星同学一直以来对我的帮助感谢 Velocious Informatics Judge Online System 为我提供例题 1感谢 Peking University Onlinejudge 为我提供例题 2感谢浙江省镇海中学的谢天同学为我提供 HNOI2008 试题感谢董华星同学提供例题 4忠心感谢！
