用单调性优化动态规划

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