问题描述：
给定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点时，i
j个点到达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;
}