LA4987 EvacuationPlan 疏散计划（dp+贪心）

野性酷女 2021-11-17 02:52 158阅读 0赞

## 题意：n个施工队，m个避难所，在一个正x坐标轴上，给出每个施工队坐标和每个避难所坐标，要求每个施工队到一个避难所避难，且每个避难所至少有一个施工队，求所有施工队所走的距离和的最小值。 ##

## 分析：先把施工队和避难所排个序，dp\[i\]\[j\]表示前i个施工队用j个避难所的最小花费。转移方程为dp\[i\]\[j\] = min(dp\[i-1\]\[j\],dp\[i-1\]\[j-1\])+abs(a\[i\].x-b\[j\].x)。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 4004;
    ll d[N];
    bool path[N][N];
    int first = 1;
    
    struct nd{
        int num,id;
        bool operator < (const nd &tp) const
        {
            return num<tp.num;
        }
    }a[N],b[N];
    
    int ans[N];
    
    void print(int n,int m)
    {
        if(n == 0 || m == 0) return ;
        print(n-1,m - path[n][m]);
        ans[a[n].id] = b[m].id;
    }
    
    int main()
    {
        int n,m;
        while(~scanf("%d",&n))
        {
            for(int i = 1;i<=n;i++)
            {
                scanf("%d",&a[i].num);
                a[i].id = i;
            }
            scanf("%d",&m);
            for(int i = 1;i<=m;i++)
            {
                scanf("%d",&b[i].num);
                b[i].id = i;
            }
            sort(a+1,a+1+n);
            sort(b+1,b+1+m);
            for(int i = 0;i<=n;i++)
                d[i]=2e18;
            d[1] = abs(a[1].num - b[1].num);
            for(int i = 2;i<=n;i++)
            {
                for(int j = min(m,i);j>=1;j--)
                {
                    if(d[j]<=d[j-1])
                    {
                        d[j] = d[j] + abs(a[i].num - b[j].num);
                        path[i][j] = 0;
                    }
                    else
                    {
                        d[j] = d[j - 1] + abs(a[i].num - b[j].num);
                        path[i][j] = 1;
                    }
                }
            }
            printf("%lld\n",d[m]);
            print(n,m);
            for(int i = 1;i<=n;i++)
                if(i==1) printf("%d",ans[i]);
                else printf(" %d",ans[i]);
            puts("");
        }
        return 0;
    }