POJ 1485

제목: n개 가공 공장, m개 원료 공장, 원료 공장 주소와 가공 공장이 일치하고 m<=n, 최적 분배를 구하여 모든 가공 공장이 그와 가장 가까운 원료 공장에 도착하고 총 거리를 최소화한다.
문제풀이: dp[i][j]는 전 i개 공장, j개 원료 공장의 최적 분배의 총 대가이다.또한 가공 공장 구간 [a, b]을 원료 공장으로 덮는 방법은 가장 중간의 그 점에 세워야 한다. 이렇게 하면 좌우 공장 수가 같고 그 거리의 합이 가장 작다.
dp[i][j]=min(dp[k][j-1]+ds[k+1][i]), 공장 위치는 (k+1+i)/2위치에 있고pre[i][j]로 이 원료 공장과 관련된 구간의 왼쪽 단점을 기록할 수 있으며 마지막으로 다시 계산하면 됩니다.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=202,K=202,inf=0x3f3f3f3f;
int d[N],dp[N][K],pre[N][K],ds[N][N];
struct data
{
    int depot,from,to;
    data(){}
    data(int _d,int _f,int _t){depot=_d;from=_f;to=_t;}
    bool operator<(const data &ne)const
    {
        return depot<ne.depot;
    }
}po[N];
int cal(int i,int j)
{
    int ans=0,t=d[(i+j)>>1];
    while(i<=j)
        ans+=abs(t-d[i++]);
    return ans;
}
int main()
{
    int n,m,ca=0;
    while(scanf("%d%d",&n,&m),n||m)
    {
        for(int i=1; i<=n; i++)
            scanf("%d",d+i);
        memset(dp,0x3f,sizeof(dp));
        memset(pre,-1,sizeof(pre));
        memset(ds,0,sizeof(ds));
        d[n+1]=inf;d[0]=-inf;
        for(int i=1;i<n;i++)
            for(int j=i+1;j<=n;j++)
                ds[i][j]=cal(i,j);
        for(int i=1;i<=n;i++)
            dp[i][1]=ds[1][i];
        for(int i=2; i<=n; i++)
            for(int j=2; j<=m; j++)
                for(int k=1,tp;k<i;k++)
                    if(dp[i][j]>(tp=dp[k][j-1]+ds[k+1][i]))
                        dp[i][j]=tp,pre[i][j]=k;
        printf("Chain %d
",++ca);
        int nu=0;
        for(int i=n,j=m,k;j!=0;)
        {
            k=pre[i][j];
            if(k==-1)
                k=0;
            po[nu++]=data((k+i+1)/2,k+1,i);
            i=k;
            j--;
        }
        sort(po,po+nu);
        for(int i=0; i<nu; i++)
        {
            printf("Depot %d at restaurant %d serves restaurant",i+1,po[i].depot);
            if(po[i].from==po[i].to) printf(" %d
",po[i].from);
            else printf("s %d to %d
",po[i].from,po[i].to);
        }
        printf("Total distance sum = %d

",dp[n][m]);
    }
    return 0;
}