《从一类单调性问题看算法的优化(汤泽)》由会员分享，可在线阅读，更多相关《从一类单调性问题看算法的优化(汤泽)（14页珍藏版）》请在金锄头文库上搜索。
1、从一类单调性问题看算法的优化湖南省长沙市第一中学 汤泽关键字】数据关系 队列 单调性摘要】充分挖掘数据关系，往往是构造出优秀算法的关键因素。本文从单调性入手, 详细讨论了允许在表的尾端进行插入，而在两端删除元素的特殊队列对一类单调 性问题的优化方法，并以此说明充分利用数据关系对构造优秀算法的重要性。【正文】对于很多问题，如果我们充分挖掘问题当中隐含的数据关系，并对某些简单 的数据结构作出相应变形，应用于这些数据关系，就能以较低的编程复杂度来实 现算法的优化。本文将通过一种特殊队列在一类单调性问题中的运用，来讨论这 种思想的具体应用。队列是一种我们非常熟悉的数据结构。最常见的队列是一种先进先出的
2、线性 表：它只允许在表的一端进行插入，而在另一端删除元素。我们对这种常见队列 稍作变形，构造出一个特殊队列：它允许在表的尾端进行插入，而在两端删除元 素。对于一些问题，如果能够挖掘出问题中隐含的单调关系，这种特殊队列能够 很好地帮助我们完成算法的优化。一、在动态规划问题中的应用运用单调性和这种特殊队列进行优化的例子最常见于动态规划问题当中。有 些动态规划问题，可以利用决策的单调性，运用这种特殊队列来实现“降一维”。 下面是一个具体的问题。【问题一】锯木场选址（CE0I2004）从山顶上到山底下沿着一条直线种植了 n 棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到
3、锯木厂。木材只能按照一个方向运输：朝山下运。山脚下有一个锯木厂。另外两个锯 木厂将新修建在山路上。你必须决定在哪里修建两个锯木厂，使得传输的费用总 和最小。假定运输每公斤木材每米需要一分钱。任务你的任务是写一个程序：从标准输入读入树的个数和他们的重量与位置计算最小运输费用将计算结果输出到标准输出输入输入的第一行为一个正整数n树的个数（2WnW20 000）。树从山顶到 山脚按照1,2n标号。接下来n行，每行有两个正整数（用空格分开）。第i+1行含有：w第i棵树的重量（公斤为单位）和d第i棵树和第i+1ii棵树之间的距离，1Ww W10 000,0Wd W10 000。最后一个数d，表示第nii
4、Zn棵树到山脚的锯木厂的距离。保证所有树运到山脚的锯木厂所需要的费用小于2000 000 000分。输出只有一行一个数12213311321126样例输入91 1输出26在解决这一问题时，首先我们要明确，将锯木厂建立在相邻两棵树之间是没 有任何意义的，否则我们可以将这样的锯木厂上移到最近的一棵树处，此时运送 上方树木的费用减少，运送下方树木的费用没有变化，总费用降低。为了方便讨论，我们先作如下定义：假设山脚锯木场处也有一棵树，编号为n +1，并且wn +1 = dn +1 = 0。 sumwi表示第1棵树到第i棵树的质量和，即sumwi=工w j。sumdi表示第1棵树到第i棵树的距离，即su
5、mdi = 2d j。特别的，有sumd1 = 0，表示第 1 棵树到自己的距离为 0。ci表示在第i棵树处建一个锯木厂，并且将第1到第i棵树全部运这个锯木场所需的费用。则wi, j = ci - c j - su伐木场所需的费用。显然有ci = ci -1 + sumwi -1 x di -1。特别的，有c1 = 0。 wi, j表示在第i棵树处建一个锯木场，并且将第j +1到第i棵树全部运往 mw j x (sumdi - sumd j)。特别的，当 i = j 时 wi, j = ci。综上可知，求出所有sumwi, sumd ii的时间复杂度为O(n)，此后求任意wi, j的时间复杂度
6、都为0(1)。设f i 表示在第i棵树处建立第二个锯木场的最小费用，则有 八)f i = min cj + wi, j + wn +1,i。直接用这个式子计算的时间复杂度为1= j i-1进行优化。猜想O(n2)，由于问题规模太大，直接使用这一算法必然超时，因此我们必须对算法 论如何进行优化以前，我们首先证明下面这一猜想。果在位置i建设第二个锯木厂，第一个锯木厂的位置是j时最优。那么如果在位置i +1建设第二个锯木厂,第一个锯木厂的最佳位置不会小于j。证明：令 sk, i表示决策变量取 k 时 f i的值，即 sk, i = ck + wi, k + wn +1, i。设k1 k2，则有sk1
7、,i - sk2,i = sumwk2 x (sumdi - sumdk2) - sumwk1x (sumdi - sumdk1)若 skl,i sk2, i 0，贝U有sumwk2 x (sumdi - sumdk2) 一 sumwkl x (sumdi - sumdkl) sumdi我们令 gk1, k2=不等式左边，当 gkl, k2 sumdi时 skl, i - sk2, i 0，所以对于 j sumdi sumd j。证毕。由上面的证明，可以说明决策变量j是单调的，此时问题就好解决了。我 们可以维护一个特殊的队列k，这个队列只能从队尾插入，但是可以从两端删除。 这个队列满足kl k
8、2 k3 . kn 以及 gk1,k2 gk2,k3 . gkn -1,kn。1计算状态f i前，若gkl,k2 0，即决策kl没有k2优，应当删除，直至gk1,k2 smdi。2 计算状态 f i时，有 f i二 ckl + wi, kl + wn +1, i。3 计算状态f i后向队列在kn比kn -1优之前i就将新的决策i。若gkn -1, kn gkn, i，表示优，kn没必要保存。因此删除kn，直至gkn -1, kn gkn, i。f i计算的复杂度都为0(1),维护队列*的总复杂度为0(),因每个状态r此整个算法的时间复杂度为O(n)。问题得到解决！本例直接利用决策的单调性，运用
9、这一特殊的队列成功地将算法的复杂度降 低，而有的动态规划问题，虽然表面上看起来决策不单调，无法直接套用上面介 绍的优化方法，但是只要充分挖掘条件中隐含的单调关系，并对数据作出相应的 调整变形，仍然可以利用类似的方法实现时间上的“降维”。【问题二】货币兑换(B0I2003)你每天会收到一些货币A，可能正也可能负，银行允许你在某天将手头所有 的货币A兑换成B。第i天的兑换比率是1 A : i B，同时你必须再多付出t B 被银行收取。在 N 天你必须兑换所有持有的货币 A。任务找一个方案使第N天结束时能得到最多的货币B输入文件第一行是整数N,T第二行是N个整数Ai,表示第i天开始时得到Ai的A币输
10、出文件将最终得到的最多的B货币数写到文件数据范围 1 W N W 34 567 0 W T W 34 567 样例输入7 1-10 3 -2 4 -6 2 3样例输出我们很容易得到问题的基本解决方法:17suma0 = 0定义sumai表示第一天到第i天心戈得到了多少A币，特别的，有卜分割点，并且将第j +1天到第i天得到的A币进wi, j表示以第i天作为行一次性兑换可以得到的B币数。则wi, j = (sumai-suma j)* i，特别的，当 i = j 时，有 wi, j = ai* i。求出所有sumai的时间复杂度为O(n)，此后求任意wi, j的时间复杂度都 为 0(1)。设 f
11、i 表示以第 i 天作为一个分割点，最多可以得到多少个 B 币。则f i = min f j + wi, j T。直接用这个式子计算的时间复杂度为O(n2)，不0=ji1能满足要求。由于本题中ai可正可负，使得suma不满足单调性，只要推倒一下就会发现，我们不能像上一题一样证明出决策的单调性。因此我们好像无法采用上例中相同的方法来实现“降一维”。 但我们很自然地联想到，如果可以通过一定的变换，将 Ai 的值变为全部非 负或者非正，问题就迎刃而解了。注意到这样一个条件：第i天的兑换比率是1 A : i B,也就是说，时间越 往后，A币越值钱。也就是说，A币兑换B币的比率是单调的!利用这一重要条件
12、作为突破口，考虑一种贪心的思想：如果当前手上的 A 币数为正，那么我们可以不忙着将其换成 B 币，因为留到以后再换，不但可以减 少T的消耗，还可以使得兑换的比例更高。基于这种思想，我们很自然地得到了 如下猜想。猜想若a.序列中有一段连续的子序列ai,ai+l,aj(ivj),ai，ai +ai+1，ai +ai+1 + ai + 2,ai + ai +1 +a j 1，均为非负数，而a乜时七aj 为负数，则当在第i天收到了 ai 的货币A后,一定存在某个最优方案,使得我们不急于在第i天兑换，而是继续在第i +1天收到a的A币，第i + 2天收到a的 i+1i+2情况决定是否兑换。这个猜想可以用
13、反证法得到i证明：直到第j天收到a的A币，再看j，下面给出证明。假设某个最优方案在i, j)区间中，存在一个或多个兑换点，设最早的一个 兑换点在第k天。那么设从上次兑换点到第i-1天为止，共余下了 x的A币，贝U：情况_；“取消这个兑换点，将其并入后一个兑换点一起兑换，既提咼了手中A 币的价值，又省去了一次兑换手续费T。情况二：x为负数：将这个兑换点提前至第i-1天，提前脱手了负数的A:x为非负数：那么显然到第k天的兑换点我们余下的钱将不会小于x，币，相应地可以使付出的B币减少，而且将区间i,k内的非负数归入下一个兑换点，得到的收益不会比原来少。综上两种情况，无论如何我们都可以通过调整将第k天的兑换点去掉，收 入却没有减少或者更高，因此假设不成立，前面的猜想得到了证明。这个猜想告诉我们，如果a非负，我们不用急着兑换，而是等到第2天,看al+ a2,如果还是非负，继续考虑第3天，第4天，直到出现最小的i, 满足a1+ a2+ ai 0 （如果找不到这样的i，贝U令i = n ）。显然一定存在某 个最优方案，使得第1到第i-1天均不是兑换点。因此，我们可以将序列 a1,a2ai压缩成一个数c1。类似地，我们继续从第i +1天考虑起，找到 一个最小的j，满足ai +1 + ai + 2+ aj 0 （如果不存在，则令j二n ）。同 样的道理，第i +1到第j -1
