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

注意输出格式。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]