ZJU/ZOJ 1196 Fast Food 解题报告

题目大意是给出位于一直线上的n家餐厅与原点的距离，要求在其中选k家作为供应站，输出供应所有餐厅的最短路程。

如果用f[i,j]表示在前j家餐厅设立i个供应站时，供应j家餐厅的最短路程，则很容易想到f[i,j]=min(f[i-1,k]+g[k+1,j])(k<j);g[k+1,j]表示在第k+1到第j家餐厅设立一个供应站，供应这些餐厅的最短路程。显然这一供应站应该设立在中点，因此进行这一预处理后就可以进行DP了。

1649566 2008-09-23 17:00:00 Accepted 1196 FPC 10 584 IwfWcf