問(wèn)題描述：
給定n個(gè)點(diǎn)在直線上的距離，然后讓你選擇其中的p個(gè)點(diǎn)建立飯店，要求其他點(diǎn)都選擇一家離自己最近的飯店供應(yīng)，求總路程最短。
解題思路：
這道題目沉積很久了，去年就看到，但是一直不敢做，主要還是因?yàn)槭荄P，有點(diǎn)怕，寒假有一天拿過(guò)來(lái)做了一下，發(fā)現(xiàn)其實(shí)不是很難，于是開始推狀態(tài)轉(zhuǎn)移，當(dāng)時(shí)的思路用是dp[i][j]表示第i個(gè)飯店建在第j個(gè)位置的最優(yōu)解，想想沒(méi)錯(cuò)，于是開始狀態(tài)轉(zhuǎn)移，中途需要一些輔助數(shù)組，dis[i][j]表示當(dāng)飯店建在i點(diǎn)時(shí)，i~j之間所有點(diǎn)到i點(diǎn)的距離和，opt[i][j]表示當(dāng)i和j均建立飯店時(shí)，兩者之間的點(diǎn)取飯店的最小和，因?yàn)樵趇和j之間的點(diǎn)取的距離必定是兩者的小值，于是可以統(tǒng)計(jì)出總和最小的值，于是就有狀態(tài)轉(zhuǎn)移方程
dp[i][j] = min{ dp[i-1][k] - dis[k][v] + dis[j][v] + opt[k][j], 1 <= k < j }
但是一直WA，就奇怪了，先放了一下。
今天再看一遍原來(lái)的代碼，想了一下實(shí)在無(wú)懈可擊了，于是開始檢查代碼，發(fā)現(xiàn)一個(gè)下標(biāo)寫錯(cuò)了，改了后就AC了，狂暈~~
代碼如下：
#include <iostream>
using namespace std;
int line[301], v;
int p;
int dp[40][310]; //保存最優(yōu)解
int route[40][310]; //記錄路徑
int dis[310][310]; //dis[i][j] 表示飯店建在i點(diǎn)時(shí)，i
j個(gè)點(diǎn)到達(dá)i點(diǎn)的總距離和
int opt[310][310]; //opt[i][j] 表示當(dāng)i和j分別建立一個(gè)飯店時(shí)它們之間的飯店取向最優(yōu)值
int cas;
int MIN(int a, int b){
return a < b ? a : b;
}
//DP
int Solve()
{
int Min = -1;
int i, j, k;
for(i = 1; i <= v; i++){
dis[i][i] = 0;
for(j = i-1; j >= 1; j--){
dis[i][j] = dis[i][j+1] + (line[i] - line[j]);
}
for(j = i+1; j <= v; j++){
dis[i][j] = dis[i][j-1] + (line[j] - line[i]);
}
}
memset(route, -1, sizeof(route));
for(i = 1; i <= 30; i++)
for(j = 1; j <= 300; j++)
dp[i][j] = -1;
for(i = 1; i <= v; i++){
dp[1][i] = dis[i][1] + dis[i][v];
if(Min == -1 || dp[1][i] < Min)
Min = dp[1][i];
}
if(p == 1){
return Min;
}
Min = -1;
for(i = 1; i <= v; i++){
opt[i][i] = 0;
for(j = i+1; j <= v; j++){
opt[i][j] = 100000000;
if(j == i + 1)
opt[i][j] = 0;
else {
for(k = i; k < j; k++)
opt[i][j] = MIN( opt[i][j], dis[i][k] + dis[j][k+1] );
}
}
}
for(i = 2; i <= p; i++){
for(j = 1; j <= v; j++){
for(k = 1; k < j; k++){
int buf;
buf = dp[i-1][k];
if(buf < 0)
continue;
buf -= dis[k][v];
buf += dis[j][v];
buf += opt[k][j];
if(buf < dp[i][j] || dp[i][j] == -1)
{
dp[i][j] = buf;
route[i][j] = k;
}
}
if(i == p && dp[i][j] != -1){
if(dp[i][j] < Min || Min == -1)
Min = dp[i][j];
}
}
}
return Min;
}
int stack[100], top;
//路徑輸出
void Output(int Value)
{
int i, j, pre, next;
printf("Chain %d\n", cas++);
for(i = 1; i <= v; i++){
if(dp[p][i] == Value)
break;
}
pre = i;
top = 0;
while(pre != -1){
stack[ top++ ] = pre;
pre = route[p-top+1][pre];
}
next = v;
for(i = 0; i < top; i++){
printf("Depot %d at restaurant %d serves restaurant", i+1, stack[ i ]);
if(i < top - 1){
for(j = next; j >= 1; j--)
if(abs( line[j]-line[ stack[i] ] ) > abs( line[j]-line[ stack[i+1] ] ))
break;
if(j+1 == next)
printf(" %d\n", next);
else
printf("s %d to %d\n", j+1, next);
next = j;
}else
{
if(next == 1)
printf(" %d\n", 1);
else
printf("s 1 to %d\n", next);
}
}
printf("Total distance sum = %d\n", Value);
}
int main()
{
int i, j, k;
cas = 1;
while(scanf("%d %d", &v, &p) != EOF){
if(!v && !p) break;
for(i = 1; i <= v; i++)
scanf("%d", &line[i] );
Output(Solve());
puts("");
}
return 0;
}