PekingUniversityOJ No.1485

这是一道很典型的动态规划问题。
动态规划在上课的时候说实话没怎么理解其精髓，于是挑一道典型题来练一下。

题目描述

Description

The fastfood chain McBurger owns several restaurants along a highway. Recently, they have decided to build several depots along the highway, each one located at a restaurant and supplying several of the restaurants with the needed ingredients. Naturally, these depots should be placed so that the average distance between a restaurant and its assigned depot is minimized. You are to write a program that computes the optimal positions and assignments of the depots.

To make this more precise, the management of McBurger has issued the following specification: You will be given the positions of n restaurants along the highway as n integers d1 < d2 < … < dn (these are the distances measured from the company’s headquarter, which happens to be at the same highway). Furthermore, a number k (k <= n) will be given, the number of depots to be built.

The k depots will be built at the locations of k different restaurants. Each restaurant will be assigned to the closest depot, from which it will then receive its supplies. To minimize shipping costs, the total distance sum, defined as

n
∑ |di - (position of depot serving restaurant i)|
i=1

must be as small as possible.

Write a program that computes the positions of the k depots, such that the total distance sum is minimized.
Input

The input file contains several descriptions of fastfood chains. Each description starts with a line containing the two integers n and k. n and k will satisfy 1 <= n <= 200, 1 <= k <= 30, k <= n. Following this will n lines containing one integer each, giving the positions di of the restaurants, ordered increasingly.

The input file will end with a case starting with n = k = 0. This case should not be processed.
Output

For each chain, first output the number of the chain. Then output an optimal placement of the depots as follows: for each depot output a line containing its position and the range of restaurants it serves. If there is more than one optimal solution, output any of them. After the depot descriptions output a line containing the total distance sum, as defined in the problem text.

Output a blank line after each test case.
Sample Input

6 3
5
6
12
19
20
27
0 0
Sample Output

Chain 1
Depot 1 at restaurant 2 serves restaurants 1 to 3
Depot 2 at restaurant 4 serves restaurants 4 to 5
Depot 3 at restaurant 6 serves restaurant 6
Total distance sum = 8

解题思路

动态规划的核心是要找到一个递推方程。
而这道题则需要局部最优状态的递推方程。考虑到局部最优状态mindis[i][j]，表示前i个餐馆
分配j个仓库的最短距离。那么，当我们增加一个仓库时：
计算MIN(mindis[l][j]+第l+1到第i个餐馆分配一个仓库的最短距离)其中j<l<i
则得到mindis[i][j+1]

其实总结起来递推方程即为mindis[i][j]=MIN(mindis[l][j-1]+onedepot[l+1][i])

其中onedepot[l+1][i]代表第l+1个餐馆到第i个餐馆只安排一个仓库的最短距离，而这个最短距离是很好算的
最短距离一定是仓库放在中间餐馆时的距离，偶数个餐馆则中间两个餐馆的任意一个都可以。
这里只需要求（i+j）/2留下的整数即可。

代码如下：

#include <iostream>
#include <stdio.h>
using namespace std;
int n,k;
int countt=0;
int restaurant[200],mindis[200][30],onedepot[200][200];
int from[200][30],to[200][30],depot[200][30];

int result(int i,int j){
    if(j<=0)
        return 1;
    int counttt=result(from[i][j]-1,j-1); //from[i][j]-1就是去掉最后一个仓库分配的餐馆，剩下的最“右”一个餐馆
    //我原来竟然想result(i-t;j-1)这里t去从1开始尝试，直到to[i-t][j-1]=i-t为止...好蠢
    printf("Depot %d at restaurant %d serves ",counttt,depot[i][j]);
    if(from[i][j]==to[i][j])printf("restaurant %d\n",from[i][j]);
    else printf("restaurants %d to %d\n",from[i][j],to[i][j]);
    return counttt+1;
}
int main(){
    while(1){
        memset(restaurant,0,sizeof(restaurant));
        memset(mindis,0,sizeof(mindis));
        memset(onedepot,0,sizeof(onedepot));
        int i,j,l,temp;
        countt++;
        cin>>n>>k;
        if(n==0&&k==0)
            break;
        for(i=1;i<=n;i++){
            cin>>restaurant[i];
        }
        for(i=1;i<=n;i++){       //计算出所有dept 其中onedepot[i][j]代表第i--j个餐厅放置一个仓库的最短距离
            for(j=1;j<=n;j++){
                for(l=i;l<=j;l++){
                    onedepot[i][j]=onedepot[i][j]+abs(restaurant[(i+j)/2]-restaurant[l]);
                }

               // cout<<i<<"  "<<j<<"   "<<onedepot[i][j]<<endl;
            }
        }
        for(i=1;i<=n;i++){
            mindis[i][0]=100000;  //递归方程的初始化
        }
        for(i=1;i<=n;i++){
            for(j=1;j<=i&&j<=k;j++){
                mindis[i][j]=100000;//首先将初始值赋为MAX
                for(l=j-1;l<i;l++){
                    temp=mindis[l][j-1]+onedepot[l+1][i]; //mindis[i][j]=min(mindis[l][j-1]+onedepot[l+1][i])
                    if(temp<mindis[i][j]){
                        mindis[i][j]=temp;
                        from[i][j]=l+1;
                        to[i][j]=i;
                        depot[i][j]=(l+1+i)/2;
                        
                    }
                }
            }
        }
        printf("Chain %d\n",countt);
        result(n,k);
        printf("Total distance sum = %d\n\n",mindis[n][k]);
    }
    return 0;
}