《POJ 1160 Post Office》由会员分享，可在线阅读，更多相关《POJ 1160 Post Office（9页珍藏版）》请在金锄头文库上搜索。
1、Post Office 解题报告解题报告00130004 杭杰北京大学信息管理系Post Office 题目重述题目重述l在一条高速公路边上有V个村庄，用一条坐标轴来描述这条公路，每个村庄的坐标各不相同，且都是整数。两个村庄间的距离用他们的坐标值差的绝对值表示。现在要在这些村庄中选出P个建立邮局，邮局建立在村庄里，每个村庄使用离他最近的那个邮局。求一种建设方案，使得所有村庄到各自所使用的邮局的距离总和最小。Post Office 题目重述题目重述l输入：共两行：l第一行给出村庄数目V和邮局数目P，1=V=300，1=P=30，P=V；l第二行按递增顺序给出V个村庄的坐标x1,x2,xV，1=x
2、i=|xi-xn+1-i|.ln=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 算法设计算法设计ln=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|+|
3、xk-1-xk+1|当xr = xk或时取到最小值。l综上，此时xr = xn/2，式中表示取整。Post Office 算法设计算法设计l现在考虑Costn,m，在前n个村庄中建立m个邮局，设最优情况下前m-1个邮局覆盖的范围是第1r个村庄，第m个邮局覆盖的范围是第r+1n个村庄，则这两部分邮局的设置都必须是最优的，因此Costn,m=Costr,m-1+Dr+1,n其中Di,j表示在第i个到第j个村庄中建立一个邮局得到的最短距离总和。Post Office 算法设计算法设计l对r从1到n遍历，即可求出最优的r值。l由此得到递推关系式：Costn,m = minCosti,m-1+Di+1,n，i=m-1,m,n-1。其中Di+1,n的求法与Costn,1类似。Post Office 程序优化程序优化l考虑到Costn,m仅与Costi,m-1相关，可以用两个一维数组存储lDa,b可以利用关系式da,a=0, Da,b=Da,b-1+xb-x(a+b)/2预先计算存入一个数组。
