算法合集之《从一类单性问题看算法的优化》.doc

从一类单调性问题看算法的优化 湖南省长沙市第一中学 汤泽 【关键字】 数据关系 队列 单调性 【摘要】 充分挖掘数据关系，往往是构造出优秀算法的关键因素。本文从单调性入手，详细讨论了允许在表的尾端进行插入，而在两端删除元素的特殊队列对一类单调性问题的优化方法，并以此说明充分利用数据关系对构造优秀算法的重要性。 【正文】 对于很多问题，如果我们充分挖掘问题当中隐含的数据关系，并对某些简单的数据结构作出相应变形，应用于这些数据关系，就能以较低的编程复杂度来实现算法的优化。本文将通过一种特殊队列在一类单调性问题中的运用，来讨论这种思想的具体应用。 队列是一种我们非常熟悉的数据结构。最常见的队列是一种先进先出的线性表：它只允许在表的一端进行插入，而在另一端删除元素。我们对这种常见队列稍作变形，构造出一个特殊队列：它允许在表的尾端进行插入，而在两端删除元素。对于一些问题，如果能够挖掘出问题中隐含的单调关系，这种特殊队列能够很好地帮助我们完成算法的优化。 在动态规划问题中的应用 运用单调性和这种特殊队列进行优化的例子最常见于动态规划问题当中。有些动态规划问题，可以利用决策的单调性，运用这种特殊队列来实现“降一维”。下面是一个具体的问题。 【问题一】锯木场选址（CEOI2004） 从山顶上到山底下沿着种植了n棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。 木材只能按照一个方向运输：朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建两个锯木厂，使得传输的费用最小。运输每公斤每米需要一分钱。任务你的任务是写一个程序： 从标准输入读入树的个数和他们的重量位置 计算最小运输费用 将计算结果输出到标准输出 输入输入的第一行为一个正整数n——树的个数（2≤n≤20 000）。树从山顶到山脚按照1，2……n标号。接下来n行，每行有两个正整数（用空格分开）。第i+1行含有：wi——第i棵树的重量（公斤为单位）和 di——第i棵树和第i+1棵树之间的距离，1≤wi ≤10 000，0≤di≤10 000。最后一个数d，表示第n棵树到山脚的锯木厂的距离。保证所有树运到山脚的锯木厂所需要的费用小于2000 000 000分。 输出输出只有一行一个数：最小的运输费用。9 1 2 2 1 3 3 1 1 3 2 1 6 2 1 1 2 1 1 输出 26 在解决这一问题时，首先我们要明确，将锯木厂建立在相邻两棵树之间是没有任何意义的，否则我们可以将这样的锯木厂上移到最近的一棵树处，此时运送上方树木的费用减少，运送下方树木的费用没有变化，总费用降低。 为了方便讨论，我们先作如下定义： 假设山脚锯木场处也有一棵树，编号为，并且。 表示第1棵树到第棵树的质量和，即。 表示第1棵树到第棵树的距离，即。特别的，有，表示第1棵树到自己的距离为0。 表示在第棵树处建一个锯木厂棵树全部运往这个伐木场所需的费用。显然有。特别的，有。 表示在第棵树处建一个锯木场，并且将第到第棵树全部运往这个锯木场所需的费用。则。特别的，当时。 综上可知，求出所有与的时间复杂度为，此后求任意的时间复杂度都为。 设表示在第棵树处建立第二个锯木场的最小费用，则有。直接用这个式子计算的时间复杂度为，由于问题规模太大，直接使用这一算法必然超时，因此我们必须对算法进行优化。在讨论如何进行优化以前，我们首先证明下面这一猜想。 [猜想] 如果在位置建设第二个锯木,第一个锯木的位置是时最优那么如果在位置建设锯木,第一个锯木。 证明： 令表示决策变量取时的值，即。 设，则有 若，则有 将含K的项移到不等式左边，整理得 我们令，当时。因为，所以对于有。 证毕。 由上面的证明，可以说明决策变量j是单调的，此时问题就好解决了。我们可以维护一个特殊的队列，这个队列只能从队尾插入，但是可以从两端删除。这个队列满足以及。 1．计算状态前，若，表示，即决策没有优，应当删除，直至。 2．计算状态时，有。 3．计算状态后向队列插入新的决策。若，表示在比优之前就将比优，没必要保存。因此删除，直至。 每个状态计算的复杂度都为，维护队列的总复杂度为，因此整个算法的时间复杂度为。问题得到解决！ 本例直接利用决策的单调性，运用这一特殊的队列成功地将算法的复杂度降低，而有的动态规划问题，虽然表面上看起来决策不单调，无法直接套用上面介绍的优化方法，但是只要充分挖掘条件中隐含的单调关系，并对数据作出相应的调整变形，仍然可以利用类似的方法实现时间上的“降维”。 【问题二】货币兑换（BOI2003） 你每天会收到一些货币A，可能正也可能负，银行允许你在某天将手头所有的货币A兑换成B。第i天的兑换比率是1 A ：