《用单调性优化动态规划.doc》由会员分享，可在线阅读，更多相关《用单调性优化动态规划.doc（18页珍藏版）》请在金锄头文库上搜索。
1、JSOI2009集训队论文 用单调性优化动态规划 【摘要】单调性作为一类重要的性质，在信息学竞赛中是一种极为常见的解题突破口，也在动态规划的优化过程中起着至关重要的作用。本文主要选取了几道国内竞赛试题，探讨单调性在动态规划优化中神奇的应用。【关键字】单调性 动态规划 队列 凸线 【目录】【序言】.3【正文】.4 一什么是单调队列.4 1.单调队列的性质.5 2.单调队列有什么用.5 3.时间效率分析.5 4.为什么这样做.5 5.一些总结.6 二一些简单的例子.7 【例一】生产产品Vijos1243.7 题目描述7 解法分析7 【例二】Cut the SequencePku3017.8 题目描
2、述.8 解法分析8 小结.9 三一些更复杂的例子.10 【例三】Toy HNOI08.10 题目描述10 朴素的解法10 正确的解法10 为什么决策单调？11 【例四】Storage Zjtsc07.12 题目描述12 解法分析12 四利用凸线的单调性来优化Dp.15 【例五】货币兑换NOI2007.15 题目描述15 解法分析15【全文总结】【参考文献】【感谢】【正文】一 什么是单调（双端）队列单调队列，顾名思义，就是一个元素单调的队列，那么就能保证队首的元素是最小（最大）的，从而满足动态规划的最优性问题的需求。单调队列，又名双端队列。双端队列，就是说它不同于一般的队列只能在队首删除、队尾插
3、入，它能够在队首、队尾同时进行删除。【单调队列的性质】一般，在动态规划的过程中，单调队列中每个元素一般存储的是两个值：1. 在原数列中的位置（下标）2. 他在动态规划中的状态值而单调队列则保证这两个值同时单调。【单调队列有什么用】我们来看这样一个问题：一个含有n项的数列(n=2000000)，求出每一项前面的第m个数到它这个区间内的最小值。这道题目，我们很容易想到线段树、或者st算法之类的RMQ问题的解法。但庞大的数据范围让这些对数级的算法没有生存的空间。我们先尝试用动态规划的方法。用代表第个数对应的答案，表示第个数，很容易写出状态转移方程：这个方程，直接求解的复杂度是O(nm)的，甚至比线段
4、树还差。这时候，单调队列就发挥了他的作用：我们维护这样一个队列：队列中的每个元素有两个域position,value，分别代表他在原队列中的位置和，我们随时保持这个队列中的元素两个域都单调递增。那计算的时候，只要在队首不断删除，直到队首的position大于等于，那此时队首的value必定是的不二人选，因为队列是单调的！我们看看怎样将 插入到队列中供别人决策：首先，要保证position单调递增，由于我们动态规划的过程总是由小到大（反之亦然），所以肯定在队尾插入。又因为要保证队列的value单调递增，所以将队尾元素不断删除，直到队尾元素小于。【时间效率分析】 很明显的一点，由于每个元素最多出队
5、一次、进队一次，所以时间复杂度是O(n)。用单调队列完美的解决了这一题。【为什么要这么做】我们来分析为什么要这样在队尾插入：为什么前面那些比大的数就这样无情的被枪毙了？我们来反问自己：他们活着有什么意义？！由于是随着单调递增的，所以对于，在计算任意一个状态的时候，都不会比优，所以j被枪毙是“罪有应得”。我们再来分析为什么能够在队首不断删除，一句话：是随着单调递增的！【一些总结】对于这样一类动态规划问题，我们可以运用单调队列来解决：其中boundx随着x单调不降，而consti则是可以根据i在常数时间内确定的唯一的常数。这类问题，一般用单调队列在很优美的时间内解决。【一些简单的例子】【例一】生产
6、产品Product1问题描述有n个产品，编号为1n。要在m个机器人的手中生产完成。其中，第i个产品在第j个机器人手中的生产时间给定为。要把这些产品按照编号从小到大生产，同一个机器人连续生产的产品个数不能够超过给定的常数l。求生产完所有产品的最短时间是多少。其中n=105，m=5，l=5*104。解法分析这道题目，很容易想到一个动态规划的算法：用表示前i个产品，其中第i个产品实在第j个机器人上完成的，前i个机器人生产完成所需最短时间。,其中pj。sumx,y表示产品1到x在y机器上生产所需的时间和。这样的算法时间复杂度是，很明显不能在时限内完成，需要进行优化。我们由于j的取值范围十分小：1=j=
7、5。我们可以从这里突破。我们尝试把每一个j单独考虑，比如现在只考虑j=1的情况：那每一个决策k，他为当前要计算的状态所提供的值是，pj。我们将其进行稍微的变形：，可以发现括号内的式子是根据k所确定的一个常量，直接对应上文的单调队列的方法，省掉了枚举决策的一维，时间复杂度降为。1 选自 Vijos 1243【例二】Cut the sequence2问题描述给定一个有n个非负整数的数列a，要求将其划分为若干个部分，使得每部分的和不超过给定的常数m，并且所有部分的最大值的和最小。其中n=105。例：n=8, m=17，8个数分别为2 2 2 | 8 1 8 |1 2，答案为12，分割方案如图所示。解
8、法分析刚开始拿到这道题目，首先要读好题：最大值的和最小。首先设计出一个动态规划的方法：，其中代表把前i个数分割开来的最小代价。=，可以用二分查找来实现。直接求解复杂度最坏情况下（M超大）是的，优化势在必行。通过仔细观察，可以发现以下几点性质： 在计算状态f(x)的时候，如果一个决策k作为该状态的决策，那么可以发现第k个元素和第x个元素是不分在一组的。 bx随着x单调不降的，用这一点，可以想到什么？可以想到前面单调队列的一个限制条件。 来看一个最重要的性质：如果一个决策k能够成为状态f(x)的最优决策，当且仅当。为什么呢？其实证明非常非常容易（用到性质1），交给读者自己考虑。到此为止，我们可以这
9、样做：由于性质三，每计算一个状态f(x)，它的有效决策集肯定是一个元素值单调递减的序列，我们可以像单调队列那样每次在队2 选自Pku3017首删除元素，直到队首在数列中的位置小于等于，然后将ax插入队尾，保持队列的元素单调性。这时候问题来了，队首元素一定是最佳决策点吗？我们只保证了他的元素值最大如果扫一遍队列，只是常数上的优化，一个递减序足以将它否决。我们观察整个操作，将队列不断插入、不断删除。对于除了队尾的元素之外，每个队列中的元素供当前要计算的状态的“值”是，其中,qx代表第x个队列元素，position这代表他在原来数组中的位置，我们不妨把这个值记为t。那每一次在队首、队尾的删除就相当于
10、删除t，每一次删除完毕之后又要插入一个新的t，然后需要求出队列中的t的最小值。我们发现，完成上述一系列工作的最佳选择就是平衡树，这样每个元素都插入、删除、查找各一遍，复杂度为O(logn),最后的时间复杂度是。有一个细节：这一个单独的决策点是不能够被省掉的（仍然留给读者思考），而上述队列的方法有可能将其删除，所以要通过特判来完成。小结我们依然通过发掘单调性完成了这一道题目。和以前不同的是，这次单调队列中存的值不同，但依然可以通过平衡树或者其余数据结构完成。单调队列是一个很灵活的东西，要合理使用。下面一个章节笔者将引入决策单调性和四边形不等式等内容，浅析单调性在动态规划优化中的另外一个形式。【一
11、些复杂的例子】【例三】玩具装箱Toy3问题描述有n个玩具，要将它们分为若干组进行打包，每个玩具有一个长度lenx。每一组必须是连续的一组玩具。如果将第x到第y个玩具打包到一组，那么它们的长度，将这组玩具打包所需的代价等于。问将所有玩具打包的最小代价是多少。注意到每组玩具个数并没有限制。n=5*104。朴素的解法仍然可以很轻易的写出一个动态规划的方法：用f(x)代表将前x个玩具打包所需要的最小代价。，其中代表将的玩具打包所需的费用。时间复杂度。正确的解法 我们如果将每个状态的决策kx打印出来列成一张表，会发现：对于。这就说明，决策是单调的。 我们不妨暂且不管这是为什么，我们想通过这一单调性来在对
12、数级或者线性时间内解决本题。 由于决策是单调的，我们可以通过二分查找决策的转折点来在O(nlogn)的时间内解决本题：3 选自HNOI2008 Toy 一开始动态规划的边界是f0=0。那么，一开始所有状态的最优决策都是0（因为还没有其他状态被计算）。然后，从状态1开始逐步往后扫描，扫描到当前状态i，要保证fi已经决策完毕，可以计算出来。 现在，由于fi已经被算了出来，我们尝试寻找哪些后面的状态的决策有可能是i。注意到决策是单调的，就是说如果一个状态fx，他在1到i这么多决策中的最优决策是i，那么对于，fy在1到i之间的最优决策肯定是i。 这样，我们可以通过二分查找，确定决策i在整个区间中的决策转折点，设转折点为x，
