题目：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
注意输出格式。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 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;}