首页 > 代码库 > UVA662- Fast Food
UVA662- Fast Food
题意:在一条公路上,有n个酒店,要建造k个供给站(建造在酒店所在的位置),给出酒店的位置,求怎么样建造供给站才能使得每个酒店都能得到服务且所要走的路程最短。
思路:在i到j酒店建立一个供给站,要使得路程和最短,要将供给站建立在中间。如果i到j为偶数时,可以建立在中间两个数其中一个地方,如果是奇数时,应该建立在(i + j) / 2的地方。我们可以预处理从i到j酒店的最短路程和dis[i][j]。所以可以得到d[i][j]表示i个供给站为前j个酒店服务时的最短路程和。之后的输出可以在计算的时候加入一个记录数组,记录分割的地方,然后递归输出。
状态转移方程:d[i][j] = min(d[i][j], d[i - 1][k] + dis[k + 1][j]); (1 <= k < j)
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> typedef long long ll; using namespace std; const int MAXN = 205; const int INF = 0x3f3f3f3f; int p[MAXN], vis[MAXN][MAXN]; ll dis[MAXN][MAXN], d[MAXN][MAXN]; int n, m; void init() { memset(vis, 0, sizeof(vis)); memset(dis, 0, sizeof(dis)); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = i; k <= j; k++) dis[i][j] += abs(p[(i + j) / 2] - p[k]); for (int i = 0; i <= m; i++) for (int j = 0; j <= n; j++) d[i][j] = INF; for (int i = 1; i <= n; i++) d[1][i] = dis[1][i]; } void outPut(int cnt, int x, int y) { printf("Depot %d at restaurant %d serves ", cnt, (x + y) / 2); if (x == y) printf("restaurant %d\n", x); else printf("restaurants %d to %d\n", x, y); } void print(int x, int y) { if (x > 1) print(x - 1, vis[x][y]); outPut(x, vis[x][y] + 1, y); } int main() { int t = 1; while (scanf("%d %d", &n, &m) && n || m) { for (int i = 1; i <= n; i++) scanf("%d", &p[i]); init(); for (int i = 2; i <= m; i++) for (int j = i; j <= n; j++) for (int k = i - 1; k < j; k++) if (d[i][j] > d[i - 1][k] + dis[k + 1][j]) { d[i][j] = d[i - 1][k] + dis[k + 1][j]; vis[i][j] = k; } printf("Chain %d\n", t++); print(m, n); printf("Total distance sum = %lld\n\n", d[m][n]); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。