这个题是一道动态规划题。用dp[i][j]表示在前j个村庄建立i个邮局的最小代价，那么可以得到如下的递推方程：
dp[i][j] = min{dp[i][k] + w[k+1][j]},k = i , ......, j - 1
w[k+1][j]表示在第k+1个村庄到第j个村庄之间建立一个邮局的最小代价。根据题意是求这些村庄到这个邮局的绝对值的和，根据的高中学到的绝对值不等式然后画出区间图
可以得出一个结论，建在中间的那个村庄代价最小。w[k+1][j]可以通过预处理得到
根据dp数组的定义很容易得到dp[i][i] = 0
最后的dp[p][v]就是所求的答案
做这个提示wa了好几次，原因有两点，第一个是初始化dp数组时用了memset,没2搞清楚用法就用，结果错了好几次。
memset用法参照百度百科点击打开链接
另一个我到现在也很迷，就是dp数组的第一个参数，我本来定的是35，但是一直有问题，后来改成 305,就可以了。ac代码如下：
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int maxv = 305; int dp[maxv][maxv]; int pos[maxv]; int w[maxv][maxv]; int main() { int v, p; cin >> v >> p; for (int i = 1; i <= v; i++) cin >> pos[i]; for (int i = 1; i < v; i++) { for (int j = i + 1; j <= v; j++) { int mid = (i + j) / 2; for (int k = i; k <= j; k++) w[i][j] += abs(pos[k] - pos[mid]); } } for (int i = 0; i <= v; i++) for (int j = 0; j <= v; j++) dp[i][j] = 1000000000; for (int i = 1; i <= v; i++) { dp[1][i] = w[1][i]; dp[i][i] = 0; } for (int i = 2; i <= p; i++) { for (int j = i + 1; j <= v; j++) { for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i - 1][k] + w[k + 1][j]); } } } cout << dp[p][v] << endl; return 0; }