uva662-FastFood（递推）-mysql教程-PHP中文网

uva662-FastFood（递推）

php中文网

发布： 2016-06-07 16:00:43

原创

1290人浏览过

题目：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）。

jQuery列表递推手风琴

jQuery列表递推手风琴是一款带左右箭头切换的新闻列表手风琴样式切换特效。

查看详情

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>

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 <= n; j++) {

				f[k][j] = INF;
				for (int i = j - 1; i >= 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;
}

登录后复制