题目描述
一些村庄建在一条笔直的高速公路边上。我们用一条坐标轴来描述这条高速公路，每一个村庄的坐标都是整数，没有两个村庄坐标相同。两个村庄间的距离，定义为它们的坐标值差的绝对值。我们需要在一些村庄建立邮局――当然，并不是每一个村庄都必须建立邮局，邮局必须被建在村庄里，因此它的坐标和它所在村庄坐标相同。每个村庄便用离它最近的那个邮局，建立这些邮局的原则是：所有村庄到各自所使用的邮局的距离总和最小。
你的任务是编写一个程序，在给写了每个村庄的坐标和将要建立的邮局数之后，按照上述原则，合理地选择这些邮局的位置。
输入
输入的第一行包含两个整数；第一个整数是村庄的数目V（1<=V<=300）；第二个整数是将建立的邮局数P(1<=P<=30且P第二行递增顺序列出了V个整数。这V个整数分别表示了各村庄的位置坐标。对于每一个位置坐标X，1<=X<=10000.
输出
输出只有一个整数S，表示你所求出的所有村庄到距离它最近的邮局的距离总和。
样例输入
10 5
1 2 3 6 7 9 11 22 44 50
样例输出
9
这道题关键在dist数组的计算
#include<cmath>
#include<vector>
#include<cstdio>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 310
#define INF 2147483647
using namespace std;
int a[MAXN];
int dp[MAXN][MAXN];
int dist[MAXN][MAXN];
int n,m;
void init(){cin >> n >> m;for(int i = 1;i <= n;i++) cin >> a[i];for(int i = 1;i <= n-1; i++)for(int j = i+1; j <= n; j++)for (int k = i;k <= j ;k++){dist[i][j] += abs(a[k]-a[(i+j)/2]);}//预处理for(int i=1;i<=n;i++) dp[1][i]=dist[1][i];}
int main(){init();for(int i=2;i<=m;i++)for(int j=i;j<=n;j++){if (!dp[i][j]) dp[i][j] = INF;for(int k = i-1; k <= j-1;k++)dp[i][j] = min(dp[i-1][k]+dist[k+1][j],dp[i][j]);}cout << dp[m][n] ;return 0;
}
