感覺又是一道經(jīng)典的DP。
題意：給定v個(gè)村莊和p個(gè)郵局(v>=p)，v個(gè)村莊在一條直線上，用一個(gè)整數(shù)值表示。求最佳的布置郵局方案使得每個(gè)村莊到最近的郵局距離之和最少。
思路：狀態(tài)表示很容易想到，用opt[i][j]表示前i個(gè)郵局覆蓋前j個(gè)村莊的最小距離之和。那么狀態(tài)轉(zhuǎn)移方程應(yīng)該怎么表示呢？從當(dāng)前狀態(tài)opt[i][j]增加一個(gè)郵局，我們可以得到它到opt[i+1][j+k]的值(j+k<=v)，即我們需要知道在任意兩個(gè)村莊之間增加一個(gè)郵局的花費(fèi)是多少，這樣我們需要一個(gè)數(shù)組cost[i][j]保存在村莊i和j之間增加一個(gè)郵局所需要的花費(fèi)，這部分需要預(yù)處理一下。這樣我們就可以輕易地寫出代碼來(lái)了。
注意的地方：i>=j時(shí)顯然opt[i][j]=0,因?yàn)猷]局比村莊多。還有就是轉(zhuǎn)移方程中的opt[i+1][j+k] = opt[i][j]+cost[j+1][j+k];注意cost中是從j+1到j(luò)+k的村莊中增加一個(gè)郵局的花費(fèi)，因?yàn)榈趈個(gè)村莊的花費(fèi)已經(jīng)包含在opt[i][j]中了，開始這里寫錯(cuò)了，答案一直不對(duì)。
#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;
}