欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

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]