首页 > ACM题库 > HDU-杭电 > HDU 4362-Dragon Ball[解题报告]HOJ
2015
05-23

HDU 4362-Dragon Ball[解题报告]HOJ

Dragon Ball

问题描述 :

Sean has got a Treasure map which shows when and where the dragon balls will appear. some dragon balls will appear in a line at the same time for each period.Since the time you got one of them,the other dragon ball will disappear so he can only and must get one Dragon ball in each period.Digging out one ball he will lose some energy.Sean will lose |x-y| energy when he move from x to y.Suppose Sean has enough time to get any drogan ball he want in each period.We want to know the minimum energy sean will lose to get all period’s dragon ball.

输入:

In the first line a number T indicate the number of test cases.Then for each case the first line contain 3 numbers m,n,x(1<=m<=50,1<=n<=1000),indicate m period Dragon ball will appear,n dragon balls for every period, x is the initial location of sean.Then two m*n matrix. For the first matrix,the number in I row and J column indicate the location of J-th Dragon ball in I th period.For the second matrix the number in I row and J column indicate the energy sean will lose for J-th Dragon ball in I-th period.

输出:

In the first line a number T indicate the number of test cases.Then for each case the first line contain 3 numbers m,n,x(1<=m<=50,1<=n<=1000),indicate m period Dragon ball will appear,n dragon balls for every period, x is the initial location of sean.Then two m*n matrix. For the first matrix,the number in I row and J column indicate the location of J-th Dragon ball in I th period.For the second matrix the number in I row and J column indicate the energy sean will lose for J-th Dragon ball in I-th period.

样例输入:

1
3 2 5
2 3
4 1
1 3
1 1
1 3
4 2

样例输出:

8

#include <cstdio>
#include <algorithm>
using namespace std;
#define inf 2147483647
struct node
{
    int l,t;
    bool operator<(const node &c) const
    {
        return l<c.l;
    }
};
node p[55][1005];
int n,m,x,f[55][1005];
void make(int z)
{
    int _min,now,i;
    i=1;
    while (i<=n && p[z][i].l<p[z-1][1].l)
        f[z][i]=inf,++i;
    _min=f[z-1][1]-p[z-1][1].l;
    now=2;
    for (; i<=n; ++i)
    {
        f[z][i]=inf;
        while (now<=n && p[z-1][now].l<=p[z][i].l)
            _min=min(_min,f[z-1][now]-p[z-1][now].l),++now;
        f[z][i]=min(f[z][i],_min+p[z][i].t+p[z][i].l);
    }
    i=n;
    while (i>=1 && p[z][i].l>p[z-1][n].l)
        --i;
    _min=f[z-1][n]+p[z-1][n].l;
    now=n-1;
    for (; i>=1; --i)
    {
        while (now>=1 && p[z-1][now].l>=p[z][i].l)
            _min=min(_min,f[z-1][now]+p[z-1][now].l),--now;
        f[z][i]=min(f[z][i],_min+p[z][i].t-p[z][i].l);
    }
}
int main()
{
    int T,i,j,k;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&m,&n,&x);
        for (i=1; i<=m; ++i)
            for (j=1; j<=n; ++j)
                scanf("%d",&p[i][j].l);
        for (i=1; i<=m; ++i)
            for (j=1; j<=n; ++j)
                scanf("%d",&p[i][j].t);
        for (i=1; i<=m; ++i)
            sort(p[i]+1,p[i]+n+1);
        for (i=1; i<=n; ++i)
            f[1][i]=abs(x-p[1][i].l)+p[1][i].t;
        for (i=2; i<=m; ++i)
            make(i);
        int ans=inf;
        for (i=1; i<=n; ++i)
            ans=min(ans,f[m][i]);
        printf("%d\n",ans);
    }
    return 0;
}