英雄哪里出來

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

解題思路：

這道題目沉積很久了，去年就看到，但是一直不敢做，主要還是因為是DP，有點怕，寒假有一天拿過來做了一下，發現其實不是很難，于是開始推狀態轉移，當時的思路用是dp[i][j]表示第i個飯店建在第j個位置的最優解，想想沒錯，于是開始狀態轉移，中途需要一些輔助數組，dis[i][j]表示當飯店建在i點時，i~j之間所有點到i點的距離和，opt[i][j]表示當i和j均建立飯店時，兩者之間的點取飯店的最小和，因為在i和j之間的點取的距離必定是兩者的小值，于是可以統計出總和最小的值，于是就有狀態轉移方程
dp[i][j] = min{ dp[i-1][k] - dis[k][v] + dis[j][v] + opt[k][j], 1 <= k < j }
但是一直WA，就奇怪了，先放了一下。
今天再看一遍原來的代碼，想了一下實在無懈可擊了，于是開始檢查代碼，發現一個下標寫錯了，改了后就AC了，狂暈~~


代碼如下：

#include <iostream>

using namespace std;

int line[301], v;
int p;
int dp[40][310];           //保存最優解
int route[40][310];        //記錄路徑
int dis[310][310];         //dis[i][j] 表示飯店建在i點時，ij個點到達i點的總距離和
int opt[310][310];         //opt[i][j] 表示當i和j分別建立一個飯店時它們之間的飯店取向最優值
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;
}