ACM试题1160 Post Office.pptVIP

Post Office 解题报告杭杰 北京大学信息管理系 Post Office 题目重述 在一条高速公路边上有V个村庄，用一条坐标轴来描述这条公路，每个村庄的坐标各不相同，且都是整数。两个村庄间的距离用他们的坐标值差的绝对值表示。现在要在这些村庄中选出P个建立邮局，邮局建立在村庄里，每个村庄使用离他最近的那个邮局。求一种建设方案，使得所有村庄到各自所使用的邮局的距离总和最小。 Post Office 题目重述 输入： 共两行： 第一行给出村庄数目V和邮局数目P， 1=V=300，1=P=30，P=V； 第二行按递增顺序给出V个村庄的坐标x1,x2,…xV，1=xi=10000。 输出： 共两行： 第一行给出所有村庄到各自所使用的邮局的距离总和S； 第二行按递增顺序给出P个邮局的坐标x1,x2,…xP。 Post Office 算法设计 这是一道典型的动态规划的题目 阶段的划分标准是已安排的邮局数和覆盖的村庄数（所谓“某邮局覆盖的村庄”是指使用该邮局的村庄）。 现以Cost[i,j]表示安排前i个邮局给前j个村庄使用，通过某种安排手段，使这j个村庄分别到这i个邮局中最近的一个的距离之和的所取到的最小值。 Post Office 算法设计 先考虑最简单的情况：Cost[n，1] 设n个村庄的坐标值按递增顺序依次为x1,x2,…xn，邮局坐标为xr，考虑 |xi-xr|+|xn+1-i-xr|=|xi-xn+1-i|. n=2k，|x1-xr|+|x2-xr|+…+|x2k-xr| =|x1-xr|+|x2k-xr|+|x2-xr|+|x2k-1-xr|+… +|xk-xr|+|xk+1-xr| =|x1-x2k|+|x2-x2k-1|+…+|xk-xk+1| 当xr = xk或xr = xk+1时取到最小值 Post Office 算法设计 n=2k-1，|x1-xr|+|x2-xr|+…+|x2k-1-xr| =|x1-xr|+|x2k-1-xr|+|x2-xr|+|x2k-2-xr|+… +|xk-1-xr|+|xk+1-xr|+|xk-xr| =|x1-x2k-1|+|x2-x2k-2|+…+|xk-1-xk+1| 当xr = xk或时取到最小值。 综上， 此时xr = x[n/2]，式中[]表示取整。 Post Office 算法设计 现在考虑Cost[n,m]，在前n个村庄中建立m个邮局，设最优情况下前m-1个邮局覆盖的范围是第1~r个村庄，第m个邮局覆盖的范围是第r+1~n个村庄，则这两部分邮局的设置都必须是最优的，因此 Cost[n,m]=Cost[r,m-1]+D[r+1,n] 其中D[i,j]表示在第i个到第j个村庄中建立一个邮局得到的最短距离总和。 Post Office 算法设计 对r从1到n遍历，即可求出最优的r值。 由此得到递推关系式： Cost[n,m] = min{Cost[i,m-1]+D[i+1,n]}，i=m-1,m,…,n-1。 其中D[i+1,n]的求法与Cost[n,1]类似。 Post Office 程序优化 考虑到Cost[n,m]仅与Cost[i,m-1]相关，可以用两个一维数组存储 D[a,b]可以利用关系式d[a,a]=0, D[a,b]=D[a,b-1]+x[b]-x[(a+b)/2]预先计算存入一个数组。 * *