动态规划之队列优化.doc

《动态规划之队列优化.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划之队列优化浙江省镇海中学贺洪鸣【例1锯木场选址】（CEOI2004）从山顶上到山底下沿着一条直线种植了n棵树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。木材只能按照一个方向运输：朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建两个锯木厂，使得传输的费用总和最小。假定运输每公斤木材每米需要一分钱。任务你的任务是写一个程序：从标准输入读入树的个数和他们的重量与位置计算最小运输费用将计算结果输出到标准输出输入输入的第一行为一个正整数n——树的个数（2≤n≤20000）。树从山顶到

2、山脚按照1，2……n标号。接下来n行，每行有两个正整数（用空格分开）。第i+1行含有：vi——第i棵树的重量（公斤为单位）和di——第i棵树和第i+1棵树之间的距离，1≤vi≤10000，0≤di≤10000。最后一个数dn，表示第n棵树到山脚的锯木厂的距离。保证所有树运到山脚的锯木厂所需要的费用小于2000000000分。输出输出只有一行一个数：最小的运输费用。样例输入样例输出269122133113216211211在解决这一问题时，首先我们要明确，将锯木厂建立在相邻两棵树之间是没有任何意义的，否则我们可以将这样的锯木厂上移到最近的一棵树处，此时

3、运送上方树木的费用减少，运送下方树木的费用没有变化，总费用降低。为了方便讨论，我们先作如下定义：假设山脚锯木场处也有一棵树，编号为，并且v[n+1]=d[n+1]=0。表示第1棵树到第棵树的质量和，即。表示第1棵树到第棵树的距离，即。特别的，有，表示第1棵树到自己的距离为0。c[i]表示在第棵树处建一个锯木厂，并且将第1到第i棵树全部运往这个伐木场所需的费用。显然有c[i]=c[i-1]+sumw[i-1]*d[i-1]。特别的，有c[1]=0。w[j,i]表示在第棵树处建一个锯木场，并且将第j到第i棵树全部运往这个锯木场所需的费用。则w[j,i]=

4、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棵树处建立第二个锯木场的最小费用，则有。直接用这个式子计算的时间复杂度为，由于问题规模太大，直接使用这一算法必然超时，因此我们必须对算法进行优化。在讨论如何进行优化以前，我们首先证明下面这一猜想。[猜想]如果在位置i建设第二个锯木厂,第一个锯木厂的位置是j时最优。那么如果在位置i+1

5、建设第二个锯木厂,第一个锯木厂的最佳位置不会小于j。证明：假设第1个锯木厂建立在第j个处时,f[i]取得最优值,且此时j为f[i]取得最优值时的最小值,如下图所示.此时f[i]=c[j]+w[j+1,i]+w[i+1,n+1]则对于任意的kc[j]+w[j+1,i]+w[i+1,n+1]c[k]+w[k+1,i]>c[j]+w[j+1,i]第i至第i+1的距离第k+1至第i的总重量c[k]+w[k+1,i]+(sumw[i]-sumw[k])*d[i]>c[j]+w[j+1,i]+(sumw[i

6、]-sumw[k])*d[i]第j+1至第i的总重量,必小于第k+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]即求f[i+1]时，决策k比决策j来得差！因此，当f[i]的第一个最佳决策为j时，f[i+1]的第一个最优决策必大于等于j!1jj+1i+1in+1锯木厂C[j

7、]w[j+1,i+1]w[i+2,n+1]i+21jj+1i+1in+1锯木厂C[j]w[j+1,i]w[i+1,n+1]证毕！1kK+1i+1in+1C[k]w[k+1,i+1]w[i+2,n+1]i+21kK+1i+1in+1C[k]w[k+1,i]w[i+1,n+1]【算法的改进】令s[k,i]表示决策变量取k时f[i]的值，即s[k,i]=c[k]+w[k+1,i]+w[i+1,n+1]。设k1

8、+1])=(c[k1]+c[i]-c[k1]-sumw[k1]*(sumd[i]-sumd[k1])-(c[