感覺又是一道經典的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;
}