从一类单调性问题看算法的优化（汤泽）

2006年全国信息学冬令营讲座

从一类单调性问题看算法的优化

湖南省长沙市第一中学 汤泽

【关键字】

数据关系 队列 单调性 【摘要】

充分挖掘数据关系，往往是构造出优秀算法的关键因素。本文从单调性入手，详细讨论了允许在表的尾端进行插入，而在两端删除元素的特殊队列对一类单调性问题的优化方法，并以此说明充分利用数据关系对构造优秀算法的重要性。

【正文】

对于很多问题，如果我们充分挖掘问题当中隐含的数据关系，并对某些简单的数据结构作出相应变形，应用于这些数据关系，就能以较低的编程复杂度来实现算法的优化。本文将通过一种特殊队列在一类单调性问题中的运用，来讨论这种思想的具体应用。

队列是一种我们非常熟悉的数据结构。最常见的队列是一种先进先出的线性表：它只允许在表的一端进行插入，而在另一端删除元素。我们对这种常见队列稍作变形，构造出一个特殊队列：它允许在表的尾端进行插入，而在两端删除元素。对于一些问题，如果能够挖掘出问题中隐含的单调关系，这种特殊队列能够很好地帮助我们完成算法的优化。

一、 在动态规划问题中的应用

运用单调性和这种特殊队列进行优化的例子最常见于动态规划问题当中。有些动态规划问题，可以利用决策的单调性，运用这种特殊队列来实现“降一维”。下面是一个具体的问题。

【问题一】锯木场选址（CEOI2004）

从山顶上到山底下沿着一条直线种植了n棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。

1

2006年全国信息学冬令营讲座

木材只能按照一个方向运输：朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建两个锯木厂，使得传输的费用总和最小。假定运输每公斤木材每米需要一分钱。 任务

你的任务是写一个程序：

从标准输入读入树的个数和他们的重量与位置 计算最小运输费用 将计算结果输出到标准输出 输入

输入的第一行为一个正整数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。最后一个数dn，表示第n棵树到山脚的锯木厂的距离。保证所有树运到山脚的锯木厂所需要的费用小于2000 000 000分。 输出

输出只有一行一个数：最小的运输费用。 样例

输入 9 1 2 2 1 3 3 1 1 3 2 1 6 2 1 1 2 1 1 输出 26

在解决这一问题时，首先我们要明确，将锯木厂建立在相邻两棵树之间是没有任何意义的，否则我们可以将这样的锯木厂上移到最近的一棵树处，此时运送上方树木的费用减少，运送下方树木的费用没有变化，总费用降低。

为了方便讨论，我们先作如下定义：

2

2006年全国信息学冬令营讲座

假设山脚锯木场处也有一棵树，编号为n?1，并且w[n?1]?d[n?1]?0。

sumw[i]表示第1棵树到第i棵树的质量和，即sumw[i]??w[j]。

j?1isumd[i]表示第1棵树到第i棵树的距离，即sumd[i]??d[j]。特别的，有

j?1i?1sumd[1]?0，表示第1棵树到自己的距离为0。

c[i]表示在第i棵树处建一个锯木厂，并且将第1到第i棵树全部运往这个[i?1]?d[i?1]。伐木场所需的费用。显然有c[i]?c[i?1]?sumw特别的，有c[1]?0。

w[i,j]表示在第i棵树处建一个锯木场，并且将第j?1到第i棵树全部运往[j]?(sumd[i]?sumd[j])。特这个锯木场所需的费用。则w[i,j]?c[i]?c[j]?sumw别的，当i?j时w[i,j]?c[i]。

[i],sumd[i]与c[i]的时间复杂度为O(n)，此后求综上可知，求出所有sumw任意w[i,j]的时间复杂度都为O(1)。 设f[i]表示在第i棵树处建立第二个锯木场的最小费用，则有

f[i]?min{c[j]?w[i,j]?w[n?1,i]}。直接用这个式子计算的时间复杂度为

1??j?i?1O(n2)，由于问题规模太大，直接使用这一算法必然超时，因此我们必须对算法进行优化。在讨论如何进行优化以前，我们首先证明下面这一猜想。 [猜想] 如果在位置i建设第二个锯木厂,第一个锯木厂的位置是j时最优。那么如果在位置i?1建设第二个锯木厂,第一个锯木厂的最佳位置不会小于j。 证明：

令s[k,i]表示决策变量取k时f[i]的值，即s[k,i]?c[k]?w[i,k]?w[n?1,i]。 设k1?k2，则有

s[k1,i]?s[k2,i]?sumw[k2]?(sumd[i]?sumd[k2])?sumw[k1]?(sumd[i]?sumd[k1]) 3

2006年全国信息学冬令营讲座

若s[k1,i]?s[k2,i]?0，则有

sumw[k2]?(sumd[i]?sumd[k2])?sumw[k1]?(sumd[i]?sumd[k1])?0

将含K的项移到不等式左边，整理得

(sumw[k1]?sumd[k1]?sumw[k2]?sumd[k2])/(sumw[k1]?sumw[k2])?sumd[i] 我们令g[k1,k2]?不等式左边，当g[k1,k2]?sumd[i]时s[k1,i]?s[k2,i]?0。因为d[k]?0，所以对于j?i有g[k1,k2]?sumd[i]?sumd[j]。

证毕。

由上面的证明，可以说明决策变量j是单调的，此时问题就好解决了。我们可以维护一个特殊的队列k，这个队列只能从队尾插入，但是可以从两端删除。这个队列满足k1?k2?k3?...?kn以及g[k1,k2]?g[k2,k3]?...?g[kn?1,kn]。

1．计算状态f[i]前，若g[k1,k2]?sumd[i]，表示s[k1,i]?s[k2,i]?0，即决策k1没有k2优，应当删除，直至g[k1,k2]?sumd[i]。

2．计算状态f[i]时，有f[i]?c[k1]?w[i,k1]?w[n?1,i]。

3．计算状态f[i]后向队列插入新的决策i。若g[kn?1,kn]?g[kn,i]，表示在kn比kn?1优之前i就将比kn优，kn没必要保存。因此删除kn，直至

g[kn?1,kn]?g[kn,i]。 每个状态f[i]计算的复杂度都为O(1)，维护队列k的总复杂度为O(n)，因此整个算法的时间复杂度为O(n)。问题得到解决！

本例直接利用决策的单调性，运用这一特殊的队列成功地将算法的复杂度降低，而有的动态规划问题，虽然表面上看起来决策不单调，无法直接套用上面介绍的优化方法，但是只要充分挖掘条件中隐含的单调关系，并对数据作出相应的调整变形，仍然可以利用类似的方法实现时间上的“降维”。

【问题二】货币兑换（BOI2003）

你每天会收到一些货币A，可能正也可能负，银行允许你在某天将手头所有的货币A兑换成B。第i天的兑换比率是1 A ：i B，同时你必须再多付出t B被银行收取。在N天你必须兑换所有持有的货币A。

4

2006年全国信息学冬令营讲座

任务

找一个方案使第N天结束时能得到最多的货币B 输入文件

第一行是整数N,T

第二行是N个整数Ai，表示第i天开始时得到Ai的A币 输出文件

将最终得到的最多的B货币数写到文件 数据范围

? 1 ≤ N ≤ 34 567 ? 0 ≤ T ≤ 34 567

样例输入 7 1

-10 3 -2 4 –6 2 3 样例输出 17

我们很容易得到问题的基本解决方法： 定义suma[i]表示第一天到第i天总共得到了多少A币，特别的，有

suma[0]?0

w[i,j]表示以第i天作为一个分割点，并且将第j?1天到第i天得到的A币进

行一次性兑换可以得到的B币数。则w[i,j]?(suma[i]?suma[j])*i，特别的，当

i?j时，有w[i,j]?a[i]*i。

求出所有suma[i]的时间复杂度为O(n)，此后求任意w[i,j]的时间复杂度都为O(1)。

设f[i]表示以第i天作为一个分割点，最多可以得到多少个B币。则

f[i]?min{f[j]?w[i,j]}?T。直接用这个式子计算的时间复杂度为O(n2)，不

0??j?i?1能满足要求。

由于本题中a[i]可正可负，使得suma不满足单调性，只要推倒一下就会发现，我们不能像上一题一样证明出决策的单调性。因此我们好像无法采用上例中

5

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新小学教育从一类单调性问题看算法的优化（汤泽） 全文阅读和word下载服务。