uva662-FastFood（递推）

题目：uva662 – Fast Food（递推） 题目大意：要求在同一条路上的N家快餐店，新建K个补助站点，每个快餐店和它的补助站点的距离之和最

题目：uva662 – Fast Food（递推）

题目大意：要求在同一条路上的N家快餐店，新建K个补助站点，每个快餐店和它的补助站点的距离之和最小。并且输出路径。

解题思路：这题之前想了很久，但是却漏掉最重要的一点：一条路上【1，N】快餐店，建一个补助站的话，建在中间是最优的。那么对于一个补助站是这样的，对于两个补助站的话，就看这两个补助站提供补助的范围了。dp【k】【j】表示在前j家快餐店建了k个补助站最小的补助距离。dp【k】【j】 = Min （dp【k – 1】【i】 + s【i + 1】【j】） (I>= k – 1 && i < j) 先预处理 s[i][j] ，表示i到j建个补助站最小的补助距离。

注意输出格式。restaurant（s）。

代码：

#include #include #include typedef long long ll;const int N = 205;const int M = 35;const ll INF = 1e13;int n, m;int d[N];ll dis[N][N];ll f[M][N];int path[M][N][2];void init () {	int mid;	for (int i = 1; i <= n; i++)		for (int j = i; j <= n; j++) {			dis[i][j] = 0;			mid = (j + i) / 2;			for (int k = i; k <= j; k++) 					dis[i][j] += labs (d[k] - d[mid]);		}}void printf_ans (int k, int j) {			if (!k)				return;			printf_ans (k - 1, path[k][j][1] - 1);			if (path[k][j][1] != j)				printf("Depot %d at restaurant %d serves restaurants %d to %d\n", k, path[k][j][0], path[k][j][1], j);			else				printf("Depot %d <strong style="color:transparent">本文来源gao@daima#com搞(%代@#码@网&</strong>at restaurant %d serves restaurant %d\n", k, path[k][j][0], j);				}int main () {	int cas = 0;	while (scanf ("%d%d", &n, &m) , n || m) {		for (int i = 1; i <= n; i++)			scanf ("%d", &d[i]);		init ();			for (int i = 1; i <= n; i++) {			f[1][i] = dis[1][i];			path[1][i][0] = (1 + i) / 2;			path[1][i][1] = 1; 		}		for (int k = 2; k <= m; k++)			for (int j = k; j = k - 1; i--) {										if (f[k - 1][i] + dis[i + 1][j] < f[k][j]) {											f[k][j] = f[k - 1][i] + dis[i + 1][j];						path[k][j][0] = (i + j + 1) / 2;						path[k][j][1] = i + 1;					}				}			}		printf ("Chain %d\n", ++cas);		printf_ans (m, n);		printf ("Total distance sum = %lld\n\n", f[m][n]);	}	return 0;}

喜欢 (0)赏

[搞代码]

分享 (0)