学步园

题目链接：662 - Fast Food

题目大意:给出n,m，在一条街上有n家餐馆，然后给出n家餐馆的坐标，然在可以在餐馆的基础上建设仓库m个，为了使得每家餐馆都能最快的调用食物，要求每家餐馆到距离自己最近的仓库的距离之和最小，并输出仓库所在餐馆的序号以及所服务的餐馆范围（到该仓库取货物的餐馆）

解题思路:dp[k][i]表示前i个餐馆用k个仓库服务的最优解，dis[i][j]表示有一个仓库服务i到j个仓库的距离和（用于dp时的计算）然后就有状态转移方程dp[k][i] = min(dp[k][i], dp[k - 1][j] + dis[j + 1][i]) （j的范围为k - 1~ i - 1),然后开一个rec数组记录每次分割的餐馆序号，用于后面输出方案，需要注意的是要将dp[0][i]全部置为较大的值，防止dp[1][i]的计算错误。计算dis[i][j]时，如过j
- i为偶数，那么中间两个餐馆都可以放置仓库，如果为奇数，肯定为中间的餐馆放置仓库。

PS：自己想出的题目和看题解做出来的题目成就感不是一个档次的。

#include <stdio.h>
#include <string.h>
#define min(a,b) (a)<(b)?(a):(b)
const int N = 205;
const int K = 35;
const int MAX = 1 << 30;
int n, m, dp[K][N], dis[N][N], sta[N], rec[K][N];

void init() {
	int sum[N];
	memset(sum, 0, sizeof(sum));
	for (int i = 1; i <= n; i++) {
		scanf("%d", &sta[i]);
		sum[i] = sum[i - 1] + sta[i];
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			int mid = (i + j) / 2;
			dis[i][j] = (mid - i) * sta[mid] - sum[mid - 1] + sum[i - 1];
			dis[i][j] += sum[j] - sum[mid] - (j - mid) * sta[mid];
		}
	}
}

int solve() {
	memset(dp, -1, sizeof(dp));
	memset(rec, 0, sizeof(rec));
	for (int i = 0; i <= n; i++)
		dp[0][i] = MAX;
	for (int k = 1; k <= m; k++) {
		for (int i = k; i <= n; i++) {
			dp[k][i] = dis[1][i];
			for (int j = k - 1; j < i; j++) {
				if (dp[k - 1][j] + dis[j + 1][i] < dp[k][i]) {
					dp[k][i] = dp[k - 1][j] + dis[j + 1][i];
					rec[k][i] = j;
				}
			}
		}
	}
	return dp[m][n];
}

void put(int cas, int x, int y) {
	int mid = (x + y) / 2;
	printf("Depot %d at restaurant %d serves ", cas, mid);
	if (x == y)
		printf("restaurant %d\n", x);
	else
		printf("restaurants %d to %d\n", x, y);
}

void print(int k, int x) {
	if (k > 1)
		print(k - 1, rec[k][x]);
	put(k, rec[k][x] + 1, x);
}

int main() {
	int cas = 1;
	while (scanf("%d%d", &n, &m), n || m) {
		init();

		printf("Chain %d\n", cas++);
		int ans = solve();
		print(m, n);
		printf("Total distance sum = %d\n\n", ans);
	}
	return 0;
}