uva662-FastFood(递推)
程序员文章站
2022-06-08 16:50:12
...
题目: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 = k - 1; i--) { if (f[k - 1][i] + dis[i + 1][j]
上一篇: 三大网红营销策略分享