感觉又是一道经典的DP。
题意：给定v个村庄和p个邮局(v>=p)，v个村庄在一条直线上，用一个整数值表示。求最佳的布置邮局方案使得每个村庄到最近的邮局距离之和最少。
思路：状态表示很容易想到，用opt[i][j]表示前i个邮局覆盖前j个村庄的最小距离之和。那么状态转移方程应该怎么表示呢？从当前状态opt[i][j]增加一个邮局，我们可以得到它到opt[i+1][j+k]的值(j+k<=v)，即我们需要知道在任意两个村庄之间增加一个邮局的花费是多少，这样我们需要一个数组cost[i][j]保存在村庄i和j之间增加一个邮局所需要的花费，这部分需要预处理一下。这样我们就可以轻易地写出代码来了。
注意的地方：i>=j时显然opt[i][j]=0,因为邮局比村庄多。还有就是转移方程中的opt[i+1][j+k] = opt[i][j]+cost[j+1][j+k];注意cost中是从j+1到j+k的村庄中增加一个邮局的花费，因为第j个村庄的花费已经包含在opt[i][j]中了，开始这里写错了，答案一直不对。
#include <stdio.h>
#include <string.h>
#define N 305
int p[N], cost[N][N], opt[N][N];
inline int abs(int x)
{
return x > 0 ? x : -x;
}
int main()
{
int village, post;
while(~scanf("%d %d", &village, &post))
{
if(post >= village)
{
puts("0");
continue;
}
memset(cost, 0, sizeof(cost));
memset(opt, 127, sizeof(opt));
for(int i = 1; i <= village; i++)
scanf("%d", &p[i]);
for(int i = 1; i <= village; i++)
for(int j = i + 1; j <= village; j++)
{
int mid = (i + j) >> 1;
for(int k = i; k <= j; k++)
cost[i][j] += abs(p[k] - p[mid]);
}
for(int i = 1; i <= village; i++)
opt[1][i] = cost[1][i];
for(int i = 1; i < post; i++)
for(int j = i + 1; j <= village; j++)
{
for(int k = 1; j + k <= village; k++)
{
if(opt[i][j] + cost[j + 1][j + k] < opt[i + 1][j + k])
{
opt[i + 1][j + k] = opt[i][j] + cost[j + 1][j + k];
}
}
}
printf("%d\n", opt[post][village]);
}
return 0;
}