动态规划之队列优化

动态规划之队列优化

浙江省镇海中学 贺洪鸣

【例1锯木场选址】（CEOI2004）

从山顶上到山底下沿着一条直线种植了n 棵树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。木材只能按照一个方向运输：朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建两个锯木厂，使得传输的费用总和最小。假定运输每公斤木材每米需要一分钱。 任务

你的任务是写一个程序：

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

将计算结果输出到标准输出 输入

输入的第一行为一个正整数n ——树的个数（2≤n ≤20 000）。树从山顶到山脚按照1，2……n 标号。接下来n 行，每行有两个正整数（用空格分开）。第i +1行含有：v i ——第i 棵树的重量（公斤为单位）和 d i ——第i 棵树和第i +1棵树之间的距离，1≤v i ≤10 000，0≤d i ≤10 000。最后一个数d n ，表示第n 棵树到山脚的锯木厂的距离。保证所有树运到山脚的锯木厂所需要的费用小于2000 000 000分。 输出

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

1 2

2 1

3 3

1 1 3

2 1 6 2 1 1 2 1 1

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

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

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

][i sumw 表示第1棵树到第i 棵树的质量和，即∑==i

j j w i sumw 1][][。

][i sumd 表示第1棵树到第i 棵树的距离，即∑-==1

1

][][i j j d i sumd 。特别的，有0]1[=sumd ，表示

第1棵树到自己的距离为0。

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

w[j,i]表示在第i 棵树处建一个锯木场，并且将第j 到第i

棵树全部运往这个锯木场所需的费用。

则w[j,i]=c[i]-c[j-1]-sumw[j-1]*(sumd[i]-sumd[j-1])。特别的，当i<=j 时w[j,i]=0。

综上可知，求出所有sumw[i],sumd[i]与c[i]的时间复杂度为O(n)，此后求任意w[j,i]的时间复杂度都为O(1)。

设f[i]表示在第i 棵树处建立第二个锯木场的最小费用，则有

11

[]min {[][1,][1,1]}j i f i c j w j i w i n ≤=≤-=+++++。直接用这个式子计算的时间复杂度为)(2n O ，由于问题

规模太大，直接使用这一算法必然超时，因此我们必须对算法进行优化。在讨论如何进行优化以前，我们首先证明下面这一猜想。 [猜想]

如果在位置i 建设第二个锯木厂,第一个锯木厂的位置是j 时最优。那么如果在位置i+1建设第二个锯木厂,第一个锯木厂的最佳位置不会小于j 。 证明：假设第1个锯木厂建立在第j 个处时,f[i]取得最优值,且此时j 为f[i]取得最优值时的最小值,如下图所示.此时f[i]=c[j]+w[j+1,i]+w[i+1,n+1] 则对于任意的k

c[k]+w[k+1,i]+w[i+1,n+1]>c[j]+w[j+1,i]+w[i+1,n+1]

即求f[i+1]时，决策k 比决策j 来得差！因此，当f[i]的第一个最佳决策为j 时，f[i+1]的第一个最优决策必大于等于j!

证毕！

【算法的改进】

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

=(c[k1]+w[k1+1,i]+w[i+1,n+1])-(c[k2]+w[k2+1,i]+w[i+1,n+1]) =(c[k1]+c[i]-c[k1]-sumw[k1]*(sumd[i]-sumd[k1]) - (c[k2]+c[i]-c[k2]-sumw[k2]*(sumd[i]-sumd[k2])

=sumw[k2]*(sumd[i]-sumd[k2])- sumw[k1]*(sumd[i]-sumd[k1])

=sumd[i](sumw[k2]-sumw[k1])-(sumw[k2]*sumd[k2]-sumw[k1]*sumd[k1])

1 j

j+1 i+1 i n+1

锯木厂 C[j] w[j+1,i] w[i+1,n+1

1 K+1 i+1 i n+1

C[k] w[k+1,i] w[i+1,n+1]

1 j j+1 i+1 i n+1 锯木厂 C[j] w[j+1,i+1] w[i+2,n+1]

1

k K+1 i+1 i

n+1 C[k] w[k+1,i+1] w[i+2,n+1] c[k]+w[k+1,i]>c[j]+w[j+1,i]

c[k]+w[k+1,i]+(sumw[i]-sumw[k])*d[i]>c[j]+w[j+1,i]+(sumw[i]-sumw[j])*d[i] c[k]+w[k+1,i+1]>c[j]+w[j+1,i+1] c[k]+w[k+1,i+1]+w[i+2,n+1]>c[j]+w[j+1,i+1]+w[i+2,n+1]

第k+1至第i 的总重量 第i 至第i+1的距离 第j+1至第i 的总重量, 必小于第k+1至第i 的总重量

若s[k1,i]-s[k2,i]<0，则有：

sumd[i](sumw[k2]-sumw[k1])<(sumw[k2]*sumd[k2]-sumw[k1]*sumd[k1])

即(sumw[k2]*sumd[k2]-sumw[k1]*sumd[k1])/ (sumw[k2]-sumw[k1])> sumd[i]

或(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。

由上面已经证明的猜想，说明决策变量j是单调的，(即f[i+1]的决策j2必大于等于f[i]时的决策j1)此时问题就好解决了。我们可以维护一个特殊的队列k，这个队列只能从队尾插入，但是可以从两端删除。这个队列满足k1

1．计算状态f[i]前，若g[k1,k2]0，即决策k1没有k2优，应当删除队首,将k1,k2,指针后移，直至g[k1,k2]>sumd[i]。此时, s[k1,i]-s[k2,i]<0, 即决策k1比k2优。

2．计算状态f[i]时，直接使用决策k1,f[i]=c[k1]+w[k1+1,i]+w[i+1,n+1]。O(1)代价！（由当前的决策序列：sumd[i]

3．计算状态f[i]后向队列插入新的决策i。

若g[k p-1,k p]>g[k p,i]，此时,如果求某个f[r]时选择K p为决策,则k p-1决策必然没有k p好,即s[k p-1,r]-s[k p,r]>0 => g[k p-1,k p] g[k p,i]

=> s[k p,r]-s[i,r]>0,此时,说明决策i必然比k p来得优

表示在k p比k p-1优之前i就将比k p优，k p没必要保存。并且，根据前面的猜想，对于以后的状态，决策i也会比k p优。

因此删除k p，将指针p前移，直至g[k p-1,k p]< g[k p,i]。

队列中的元素只会入队一次，出队一次，维护队列k的总复杂度为O(n)，因此每个状态f[i]计算的均摊复杂度都为O(1)，整个算法的时间复杂度为O(n)。问题得到解决！

注意：上例的决策单调性的条件是，每棵树的重量均>0,这样，重量前缀数组sumw满足单调性,才会满足第j+1至第i的总重量,必小于第k+1至第i的总重量(k

【例2仓库建设】（浙江2007

L公司有N

如右图所示，工厂1在山顶，工厂N

L公司一般把产品直接堆放在露天，以节省

费用。突然有一天，L公司的总裁L先生接到

是不同的。第i个工厂目前已有成品Pi件，在第i个工厂位置建立仓库的费用是Ci。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于L公司产品的对外销售处设置在山脚的工厂N，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送1个单位距离的费用是1。假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据：

工厂i距离工厂1的距离Xi（其中X1=0）;工厂i目前已有成品数量Pi;在工厂i建立仓库的费用Ci;

请你帮助L公司寻找一个仓库建设的方案，使得总的费用（建造费用+运输费用）最小。【输入文件】

输入文件storage.in第一行包含一个整数N，表示工厂的个数。

接下来N行每行包含两个整数Xi, Pi, Ci, 意义如题中所述。

【输出文件】

输出文件storage.out仅包含一个整数，为可以找到最优方案的费用。

【样例输入】

3

0 5 10

5 3 100

9 6 10

【样例输出】

32

【样例说明】

在工厂1和工厂3建立仓库，建立费用为10+10=20，运输费用为(9-5)*3 = 12，总费用32。 如果仅在工厂3建立仓库，建立费用为10，运输费用为(9-0)*5+(9-5)*3=57，总费用67， 不如前者优。

【初步分析】

1.状态表示

以sump[i]表示第1个工厂至第i 个工厂中的总的产品数量；

以sumw[i]表示将第1个工厂至第i 个工厂的所有产中运至第i 个工厂的费用； 以w[i,j]表示将第i 个工厂至第j 个工厂的所有产中运至第j 个工厂的费用。

W[i,j]=sumw[j]-sumw[i-1]-sump[i-1]*(x[j]-x[i-1])

所有的sump[1..n]、sumw[1..n]可在O(n)的总次数内算出，每个w[i,j]可以O(1)算出。 以f[i]表示在第i 个工厂建立一个仓库，前i 个工厂需要的最小费用; 所求为f[n]。

2.状态转移方程

01

[]{[][1,][]}

[0]0

k i f i f k w k i c i f Min ≤≤-=+++=

时间复杂度为O(n 2)。

下面使用例1相似的方法，将算法的时间复杂度降为O(n)。

【猜想】

求f[i]函数时的决策k 关于i 单调。 证明：

假设求得f[i]时的最优决策为k,对于任意的j

[][1,][][][1,][][][1,][][1,]

[][][][]([][])[][][][]([][])[][][]([][])[][][f k w k i c i f j w j i c i f k w k i f j w j i f k sumw i sumw k sump k x i x k f j sumw i sumw j sump j x i x j f k sumw k sump k x i x k f j sumw j sump j +++<+++++<+++-+?-<+-+?--+?-<-+ ]([][])

[][][][][][][][][]([][])[][][][][][][][][1]([][])

[][][]([1][])x i x j f k sumw k sump k x k f j sumw j sump j x j x i sump k sump j f k sumw k sump k x k f j sumw j sump j x j x i sump k sump j f k sumw k sump k x i x k ?---?<--?+?-?--?<--?++?--+?+- [][][]([1][])[][1][][]([1][])[][1][][]([1][])

[][1,1][][1,1]

[][1,][1][][1,][1]

f j sumw j sump j x i x j f k sumw i sumw k sump k x i x k f j sumw i sumw j sump j x i x j f k w k i f j w j i f k w k i c i f j w j i c i <-+?+-++-+?+-<++-+?+-+++<+++++++<++++

证毕！

【算法的优化】

令s[k,i]表示当决策为k 时求f[i]的表达式的值,即s[k,i]=f[k]+w[k+1,i]+c[i]。 对于k1

[1,][2,]

[1][11,][]([2][21,][])[1][][1][1]([][1])

([2][][2][2]([][2]))

([1][1][1][1])([2][2]s k i s k i f k w k i c i f k w k i c i f k sumw i sumw k sump k x i x k f k sumw i sumw k sump k x i x k f k sumw k sump k x k f k sumw k -=+++-+++=+--?--+--?-=++?-++[2][2])[]([1][2])

[1,][2,]0,

([1][1][1][1])([2][2][2][2])[]([1][2])

([1][1][1][1])([2][2]sump k x k x i sump k sump k s k i s k i f k sumw k sump k x k f k sumw k sump k x k x i sump k sump k f k sumw k sump k x k f k sumw k sum ?-?--<++?-++?

([1][2])

p k x k x i sump k sump k ?>-

令g[k1,k2]=不等式左边的值,它只与k1和k2有关，与i 无关。

瑰丽华尔兹 NOI2005 day1 给定一个N 行M 列的矩阵，矩阵中的某些方格上有障碍物。有一个人从矩阵中的某个方格开始滑行。每次滑行都是向一个方向最多连续前进c 格（也可以原地不动）（两次滑行的c 值不一定相同）。但是这个人在滑行中不能碰到障碍物。现按顺序给出K 次滑行的方向（东、南、西、北中的一个）以及对应的c ，试求这个人能够滑行的最长距离（即格子数）。

数据范围：1≤N,M ≤200，K ≤200，

∑=k

i i

c

1

≤40000

分析：

本题是一个求最值的问题。根据题目中K次滑行的有序性以及数据范围，可以很容易设计出这样一种动态规划算法：

令f(k,x,y)=此人k次滑行后到达(x,y)方格时已经滑行的最长距离。动态规划的状态转移方程如下（以下仅给出向东滑行的状态转移方程，其他3个方向上的转移方程可以类似地推出）：

f(0,startx,starty)=0

f(k,x,y)=max{f(k-1,x,y),f(k-1,x,y-1)+1,f(k-1,x,y-2)+2,……,f(k-1,x,y’)+y-y’}

（其中y’为满足y=1或(x,y’-1)上有障碍或y’=y-c k的最大值）

从图14中可以很清楚地看出动态规划转移的条件：

现在来分析这个动态规划算法的时间复杂度。

显然，状态总数为O(KMN)，而每次状态转移在最坏情况下的时间复杂度为O(max{M,N})，因此总的时间复杂度为O(KMN*max{M,N})=O(1.6*109)，难以承受。因此，我们需要对这个动态规划算法进行优化。

先不考虑障碍，可以看出，在求f(k,x,y)与f(k,x,y+1)时，很多状态我们都重复考虑了。以图15为例，求f(k,1,3)与f(k,1,4)时都用到了f(k-1,1,2)和f(k-1,1,3). 在先前介绍的动态规划算法中，这样的重复大量出现，导致算法的低效。那么，如何才能有效地防止这类重复计算的发生呢？让我们先来研究动态规划方程：f(k,x,y)=max{f(k-1,x,y),f(k-1,x,y-1)+1,f(k-1,x,y-2)+2,……,f(k-1,x,y’)+y-y’}

对于一个具体的例子k=2，x=1，c2=2可以列出如下等式：

f(2,1,1)=max{f(1,1,1)}

f(2,1,2)=max{f(1,1,1)+1,f(1,1,2)}

f(2,1,3)=max{f(1,1,1)+2,f(1,1,2)+1,f(1,1,3)}

f(2,1,4)=max{f(1,1,2)+2,f(1,1,3)+1,f(1,1,4)}

……

如果我们定义一个序列a，使得a i=f(1,1,i)-i+1，则以上等式可以写成：

f(2,1,1)=max{a1}=max{a1}

f(2,1,2)=max{a1+1,a2+1}=max{a1,a2}+1

f(2,1,3)=max{a1+2,a2+2,a3+2}=max{a1,a2,a3}+2

f(2,1,4)=max{a1+3,a2+3,a3+3,a4+3}=max{a2,a3,a4}+3

……

显然，在应用了a序列之后，我们就可以只关注a序列而不必为每个a i加上一个不同的值，从而简化了操作。

现在，我们可以加入对障碍物的考虑。例如对于图15中的状态，我们依次要求max{a1},max{a1,a2}, max{a4}, max{a6}, max{a6,a7}, max{a6,a7,a8}, max{a7,a8,a9}. 考虑max函数中的序列，可以发现，每次都是在序列的尾部添上一个a值（遇到障碍物除外），并有时在头部删去一些a值（如果区间长度超过c k+1，就删去1个a值；

如果遇到一个障碍物，则清空整个序列），而且这个序列中a的下标一定是连续的。有了这些条件与限制，就可以运用一种专门计算区间最值的数据结构——线段树1。每次根据a值建立一棵线段树，然后对于需要求最大值的区间，直接在线段树中查找。对于一行来说，建立线段树的时间复杂度为O(M)，每次查找的时间复杂度为O(log2M)，而对于前文所说的区间处理，由于每个a值最多进入区间一次，被删除一次，所以维护区间的总的时间复杂度为O(M). 这样，整个算法的时间复杂度降为O(KMNlog2(max{m,n})).

然而，线段树的编程复杂度较高，初始化、插入、查找分别需要一个子过程，容易出错。并且O(KMNlog2(max{m,n}))的复杂度再乘以线段树操作中的系数，还是比较慢，不能令人满意。实际上，有一种基本数据结构——队列可以非常好地解决这个问题。

前面已经对于序列的插入与删除进行过讨论。其中只在一端插入，另一端删除的特性恰好符合队列的性质。但是，这里是要求队列中所有数的最大值，普通的队列可以胜任这个操作吗？让我们首先来分析一下如何存储队列中的数。

如图16所示，对于已经出现在队列中的a2与a3，如果a2≤a3，则a2是没有必要出现在队列中的。因为根据队列的插入与删除原则可以推导出，如果队列中已经出现a3了，则在a2被删除之前，a3是一定不会被删除的。因此，a2与a3会一直同时出现在队列中，直至a2被删除。但是a2≤a3，因此队列中的最大值永远不会是a2，也就没有必要存储a2.

根据这一条重要的性质，可以立刻推导出“有必要”存储在队列中的a值的大小关系——严格递减。也就是说，存储在队列中的a值是依次减小的，而队头元素的值为最大值，也就是当前队列中所有数字（无论是否存储在队列中）的最大值。这样，每次可以取出位于队头的a值作为最大值。但是一个新的问题摆在我们面前——如何实时维护队列，即如何正确地插入或删除元素。

首先研究删除操作。很显然，如果队头a值的下标对应的方格与当前处理的方格之间的距离已经大于c k，则直接将它从队列中删除，即队头指针加一。

接着是插入操作。根据前文中对于队列中元素大小关系的讨论可以得知，插入一个元素a i后，队列中不能有元素a j满足a j≤a i. 于是，我们可以从队尾开始，依次删除掉不大于a i的a值，直到队列中剩下的元素都大于a i. 此时就可以将a i插入队尾。（插入与删除过程见图17）。

1线段树是一棵以线段作为基本单位的二叉树，在线段树中进行的区间插入、删除以及询问的时间复杂度均为O(log

N). 关于线段树

2

的介绍详见参考书目[2].

很显然，每次求队列中所有元素的最大值可以直接查看队头元素。根据此队列性质，队头元素一定是队列中所有元素里最大的一个。

由于在一行中，一个元素最多被插入一次，删除一次，所以插入与删除的总时间复杂度为O(max{M,N})，而每次询问最大值的时间复杂度仅为O(1). 综上所述，此算法的时间复杂度为O(KMN)，是一个十分优秀的算法。

相应的伪代码（见下页）：

我们首先找到了一

个动态规划的解法。

但是由于每次转移

的时间复杂度太高，

使得我们必须减少

冗余运算。文中提到

的线段树是一个不

错的解决方案，但是

其编程复杂度与时

间复杂度都还不能

令人十分满意。而经

常被我们所忽略的

基本数据结构——

队列却在这里发挥

了巨大的作用。由前

文可以看出，运用队

列的解法巧妙而简

洁，不但降低了时间

复杂度，还大大减少

了由于程序复杂而

导致编程错误的可

能性，很好地解决了

这个问题。这再一次

说明，在新趋势下的信息学竞赛中，基本数据结构的作用没有减小，而是变得更加重要了。在我们找到一种

好算法而畏于其复杂的程序实现时，不妨转换思路，尝试用基本数据结构加以解决，说不定会有事半功倍的

效果。