转载于：>>>
题目大意：
一条高速公路，有N个村庄，每个村庄均有一个唯一的坐标，选择P个村庄建邮局，问怎么选择，才能使每个村庄到其最近邮局的距离和最小？最后打印这个最小值。
思路：典型的DP问题。
当我们在v个村庄中只建一个邮局，可以推导出，只有邮局位于中间位置，距离和才最小；有一个特殊情况是，当村庄数为偶数，中间位置有两个村庄，经过计算，两个村庄的距离和相等，所以俩位置均可。
可以联想到，N个村庄建P个邮局，相当于每个邮局均有一个作用范围，该邮局位于其作用范围的中间位置，就是要找到一个k，使前k个村庄建P - 1个邮局，最后几个村庄建一个邮局的方案满足题意。
那么，状态转移方程就可以写成：
dp[i][j]：前i个村庄建j个邮局的最小距离和
dis[i][j]：第i个村庄到第j个村庄之间建1个邮局的最小距离和
状态转移方程：dp[i][j] = min（dp[i][j]，dp[k][j - 1] + dis[k + 1][j]）
还有一点，计算dis[i][j]时，dis[i][j - 1]已经计算出来，而且可以推导出无论j - 1为奇数还是偶数，dis[i][j]均可以写成dis[i][j - 1] + j距离i、j中点的距离。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; #define INF 0X3f3f3f3f int N, P; int a[305];//村庄位置 int dis[305][305];//dis[i][j]表示i，j之间建一个邮局的最小距离和 int dp[305][35];//dp[i][j]表示前i个村庄建j个邮局的最小距离和 int main() { while (scanf("%d%d", &N, &P) != EOF) { for (int i = 1; i <= N; i++) { scanf("%d", &a[i]); } memset(dis, 0, sizeof(dis)); for (int i = 1; i <= N - 1; i++) { for (int j = i + 1; j <= N; j++) { dis[i][j] = dis[i][j - 1] + a[j] - a[(i + j) / 2]; //这个可以通过画图理解 } }//初始化dis[][]数组 memset(dp, INF, sizeof(dp)); for (int i = 1; i <= N; i++) { dp[i][1] = dis[1][i];//建一个邮局的情况是临界值，事先处理 } //初始化dp数组，为下面的状态转移方程做准备 for (int i = 2; i <= P; i++) {//一共建i个邮局 for (int j = i; j <= N; j++) {//1~j村庄建i个邮局 for (int k = i - 1; k <= j - 1; k++) {//1~k村庄建i-1个邮局,因为一定要留一个邮局在k~j个村庄中建 dp[j][i] = min(dp[j][i], dp[k][i - 1] + dis[k + 1][j]); } } } printf("%d\n", dp[N][P]); } return 0; }
2018-07-26
原文：https://www.cnblogs.com/00isok/p/9372472.html