[가져오기] POJ1485 Fast Food(DP)

Fast Food
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 1597
 
Accepted: 553
 
Special Judge
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

Source
Southwestern European Regional Contest 1998
 
 
[제목 대의]
한 도로에 n개의 여관이 있는데 그 중에서 k개의 설치 창고를 선택하면 한 창고는 몇 개의 여관을 서비스할 수 있고 한 여관은 창고 하나만 서비스할 수 있다.어느 여관에 창고를 설치하고 창고마다 어떤 여관을 서비스하는지 물어보면 여관에서 창고까지의 총 거리를 최소화하고 총 거리를 구할 수 있다(길이는 마지막 한 걸음만 부탁한다).
[데이터 범위]
1 <= n <= 200, 1 <= k <= 30, k <= n
[문제풀이 사상]
1. 이 문제는 뚜렷한 동태 기획 문제에 속하고 관건은 상태 이동 방정식을 찾는 것이다.
2,sum[i][j]로 전 i개 여관을 표시하고 j개 창고에서 얻은 거리와 최소치를 설정하면sum[n][k]가 요구된다.
3. sum[i][j]의 서브구조를 찾고 전 j-1개의 창고 서비스가 첫 번째부터 k번째 호텔까지 있다고 가정하면 마지막 창고 서비스 k+1개가 첫 번째 호텔까지 간다.
4. 원[i][j]로 창고 서비스 i에서 j까지 창고까지의 거리와 최소치를 나타낼 수 있다.
5. 상태 이동 방정식을 얻는다.sum[i][j]=min(sum[k][j-1]+one[k+1][i])(j-1<=k<=i-1,min은 모든 k가 받을 만한 값 중 가장 작은 값을 얻는다).
6. 문제는 원[i][j]을 구하는 것으로 전환된다. 즉, i에서 j까지의 여관에 창고의 총 거리를 설정한다.
7. i에서 j까지 모두 홀수 개의 여관이 있다고 가정하면 우리는 창고를 중간 여관, 즉 여관(i+j)/2에 놓으려고 한다. 창고를 왼쪽으로 옮기는 거리 x를 가정하면 오른쪽에 있는 모든 여관에서 창고까지의 거리는 모두 x를 더하고 일부 왼쪽 여관의 거리는 x를 줄인다. 나머지 감소는 모두 x보다 작고 심지어 감소하지 않는다.따라서 창고를 중간 위치에서 왼쪽으로 어느 위치로 옮기면 총 거리가 증가하고 오른쪽으로 옮기는 것이 같기 때문에 창고는 여관(i+j)/2에 두는 것이 가장 적합하다.
8. i에서 j까지 짝수 여관이 있다고 가정하면 창고를 (i+j-1)/2와 (i+j+1)/2에서 얻은 총 거리가 같다(대칭성). 창고를 (i+j-1)/2에 놓고 왼쪽으로 이동하면 7과 비슷한 생각으로 총 거리가 커지고 오른쪽으로 이동하는 상황이 똑같다는 것을 알 수 있다. 이로써 창고를 (i+j-1)/2에 놓으면 총 거리가 가장 작다는 것을 알 수 있다.
9, 7, 8에서 원[i][j]를 얻을 수 있으며 실제적으로 창고를 (i+j)/2로 정리하면 최소 총 거리를 얻을 수 있다.
10. 데이터 범위가 비교적 작기 때문에 우리는 모든 원[i][j]의 조합을 계산할 수 있다.
 
11. Poj는 몇 개의 호텔에 창고를 설치하고 창고마다 어떤 호텔을 서비스하는지 출력해야 하기 때문에 동적 기획 경로를 저장해야 한다.
12.at[i][j],from[i][j],to[i][j]는 각각sum[i][j]가 최소치를 받았을 때 마지막 창고의 위치, 서비스의 시작 위치와 서비스의 종료 위치를 나타낸다.
13. 귀속을 통해 결과를 출력한다.
 

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int INF=100000000;
int r[300],sum[300][40],one[300][300];

int from[300][40],to[300][40],at[300][40];

int output(int i,int j)
{
    if(j<=0||i<=0)return 1;
    int num=output(from[i][j]-1,j-1);
    printf("Depot %d at restaurant %d serves ",num,at[i][j]);
    if(from[i][j]==to[i][j])printf("restaurant %d
",from[i][j]);
    else printf("restaurants %d to %d
",from[i][j],to[i][j]);
    return num+1;
}    

int main()
{
    int n,K,i,j,k,middle;
    int iCase=0;
    while(scanf("%d%d",&n,&K)!=EOF)
    {
        iCase++;
        if(n==0&&K==0)break;
        for(i=1;i<=n;i++)scanf("%d",&r[i]);
        memset(one,0,sizeof(one));
        memset(sum,0,sizeof(sum));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                middle=(i+j)/2;
                for(k=i;k<middle;k++)one[i][j]+=r[middle]-r[k];
                for(k=middle+1;k<=j;k++)one[i][j]+=r[k]-r[middle];
            }    
        }  
        for(i=1;i<=n;i++)sum[i][0]=INF;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=i&&j<=K;j++)
            {
                sum[i][j]=INF;
                for(k=j-1;k<=i-1;k++)
                {
                    int tmp=sum[k][j-1]+one[k+1][i];
                    if(tmp<sum[i][j])
                    {
                        sum[i][j]=tmp;
                        from[i][j]=k+1;
                        to[i][j]=i;
                        at[i][j]=(k+1+i)/2;
                    }    
                }    
            }    
        } 
        printf("Chain %d
",iCase);
        output(n,K);
        printf("Total distance sum = %d

",sum[n][K]);     
    }    
    return 0;
}    

 
기사 출처:http://www.cnblogs.com/kuangbin/archive/2011/11/12/2246407.html