問題描述：
給定n個(gè)點(diǎn)在直線上的距離，然后讓你選擇其中的p個(gè)點(diǎn)建立飯店，要求其他點(diǎn)都選擇一家離自己最近的飯店供應(yīng)，求總路程最短。

解題思路：

這道題目沉積很久了，去年就看到，但是一直不敢做，主要還是因?yàn)槭荄P，有點(diǎn)怕，寒假有一天拿過來做了一下，發(fā)現(xiàn)其實(shí)不是很難，于是開始推狀態(tài)轉(zhuǎn)移，當(dāng)時(shí)的思路用是dp[i][j]表示第i個(gè)飯店建在第j個(gè)位置的最優(yōu)解，想想沒錯(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，就奇怪了，先放了一下。
今天再看一遍原來的代碼，想了一下實(shí)在無懈可擊了，于是開始檢查代碼，發(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í)，ij個(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;
}