首页 > 代码库 > poj邮局1160

poj邮局1160

题目是给出V个村庄,取出P个做为邮局,要求每个村庄到邮局的距离和最小。

先考虑只有一个邮局的情况,不管你怎么放邮局和最小的情况总是在中点的位置。

再来考虑P>1的情况:

假设P-1个邮局已经选好,那么最后一个只要在剩下的未选村庄中选择一个 使和加起来最小。

就有递推式: m[ v ][ p ]=min{ m[i][p-1]+dis[i+1][v] }

m[i][p-1]表示在前面i个村庄里选p-1个邮局的最小距离和,p-1<=i<=v ;

dis[i+1][v]表示从i+1后选出一个村庄,使得(i+1 , v)个村庄到这个村庄的距离和最小,也就是化解为

刚刚考虑的只有一个邮局的情况了,(肯定是在中点了)。

这里要注意一点:后面添加的一个邮局总是放在(i+1,v)的中点位置,dis[i+1][v]表示的是(i+1,v)  到中点的和。

我一开始以为i+1不一定是离新增加的邮局最近,那么min[i][p-1]+dis[i+1][v]就不是最小的和了。

但是后面发现虽然这样求出来的和不是最小的,但是最小的和会在下一次求解过程中得出,所以不影响结果。

poj邮局1160