首页 > ACM题库 > HDU-杭电 > HDU 3757-Evacuation Plan-动态规划-[解题报告]HOJ
2015
04-10

HDU 3757-Evacuation Plan-动态规划-[解题报告]HOJ

Evacuation Plan

问题描述 :

Flatland government is building a new highway that will be used to transport weapons from its main weapon plant to the frontline in order to support the undergoing military operation against its neighbor country Edgeland. Highway is a straight line and there are n construction teams working at some points on it.
During last days the threat of a nuclear attack from Edgeland has significantly increased. Therefore the construction office has decided to develop an evacuation plan for the construction teams in case of a nuclear attack. There are m shelters located near the constructed highway. This evacuation plan must assign each team to a shelter that it should use in case of an attack.
Each shelter entrance must be securely locked from the inside to prevent any damage to the shelter itself. So, for each shelter there must be some team that goes to this shelter in case of an attack. The office must also supply fuel to each team, so that it can drive to its assigned shelter in case of an attack. The amount of fuel that is needed is proportional to the distance from the team’s location to the assigned shelter. To minimize evacuation costs, the office would like to create a plan that minimizes the total fuel needed.
Your task is to help them develop such a plan.

输入:

The input begins with an integer T. The next T blocks each represents a case. The first line of each case contains n – the number of construction teams (1 ≤ n ≤ 4000). The second line contains n integer numbers – the locations of the teams. Each team’s location is a positive integer not exceeding 109, all team locations are different.
The third line of each case contains m – the number of shelters (1 ≤ m ≤ n). The fourth line contains m integer numbers – the locations of the shelters. Each shelter’s location is a positive integer not exceeding 109, all shelter locations are different.
The amount of fuel that needs to be supplied to a team at location x that goes to a shelter at location y is equal to |x – y|.

输出:

The input begins with an integer T. The next T blocks each represents a case. The first line of each case contains n – the number of construction teams (1 ≤ n ≤ 4000). The second line contains n integer numbers – the locations of the teams. Each team’s location is a positive integer not exceeding 109, all team locations are different.
The third line of each case contains m – the number of shelters (1 ≤ m ≤ n). The fourth line contains m integer numbers – the locations of the shelters. Each shelter’s location is a positive integer not exceeding 109, all shelter locations are different.
The amount of fuel that needs to be supplied to a team at location x that goes to a shelter at location y is equal to |x – y|.

样例输入:

1
3
1 2 3
2
2 10

样例输出:

8
1 1 2

题解:

分别对人和shelter从小到大排序之后再dp,这样可以消除后效性。

设f[i][j]表示第i个人放在第j个遮蔽物里,则有:f[i][j]=min(f[i-1][j],f[i-1][j-1])+abs(x[i]-y[j]);

可以使用滚动数组将维,降低空间复杂度。

需要注意的是,最后输出时还要再排序回来输出。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long inf=(1LL)<<60;
short path[4010][4010];
long long f[4010];
struct node
{
    long long d;
    int num;
    int sh;
}x[4010],y[4010];
int n,m;
bool cmpd(node a,node b)
{
    return a.d<b.d;
}
bool cmpnum(node a,node b)
{
    return a.num<b.num;
}
void solve(int i,int j)
{
    if(i!=1) solve(i-1,path[i][j]);
    x[i].sh=y[j].num;
}
int main()
{
    int sec;
    scanf("%d",&sec);
    for(int z=1;z<=sec;z++)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%I64d",&x[i].d);
            x[i].num=i;
        }
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%I64d",&y[i].d);
            y[i].num=i;
        }
        sort(x+1,x+1+n,cmpd);
        sort(y+1,y+1+m,cmpd);

        for(int i=0;i<=max(n,m);i++)
        f[i]=inf;
        f[1]=abs(x[1].d-y[1].d);
        for(int i=2;i<=n;i++)
         for(int j=min(i,m);j>=1;j--)
        {
            if(f[j]<f[j-1])
            {
                f[j]=f[j]+abs(x[i].d-y[j].d);
                path[i][j]=j;
            }
            else
            {
                f[j]=f[j-1]+abs(x[i].d-y[j].d);
                path[i][j]=j-1;
            }
        }
        printf("%I64d\n",f[m]);
        solve(n,m);
        sort(x+1,x+1+n,cmpnum);
        for(int i=1;i<=n-1;i++)
        printf("%d ",x[i].sh);
        printf("%d\n",x[n].sh);
    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/hyogahyoga/article/details/8043372