hdu 4362 Dragon Ball

Dragon Ball

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2204 Accepted Submission(s): 770


Problem Description 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.
Input 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.
Output For each case print a number means the minimum energy sean will lose.
Sample Input

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

Sample Output

8

Author FZU
Source 2012 Multi-University Training Contest 7



題意： m個周期，每個周期出現n個龍珠，剛開始在x位置，從x位置到y位置消耗的能量值是兩者差的絕對值+在y位 置的龍珠要吸收的能量值，每個周期必須要在一個龍珠的位置。

題解： 很容易想到動態規劃方程a[i][k].dp=min(a[i][k].dp,(a[i-1][j].dp+|a[i][k].x-a[i-1][j].x|+a[i][k].v)),這樣直接用復 雜度為O（m*n*n）會超時，需要優化，把絕對值去掉，會出現兩種情況

1.a[i][k].x>=a[i-1][j].x（前一個周期龍珠的位置小於後一個周期龍珠的位置） 這時a[i-1][j].dp-a[i-1][j].x+a[i][k].x+a[i][k].v,設mini=a[i-1][j].dp-a[i-1][j].x 此時a[i][k].dp=mini+a[i][k].x+a[i] [k].v 對a[i][k].dp,a[i][k].x和a[i][k].v為固定的，在所有的a[i][k].x>=a[i-1][j].x中，只需找到最小的mini就可以 了，此時對所有j，只需遍歷一遍j就可以了，不需要每個k都遍歷一遍j了,因為對後一個k值，其i-1行x值小於現在 的x值的，只會多在前面的基礎上多數，前面的最小的只需與後來多的比較就可以了。


2.a[i][k].x<=a[i-1][j].x（前一周期龍珠的位置大於後一個周期龍珠的位置） 這時a[i-1][j].dp+a[i-1][j].x-a[i][k].x+a[i][k].v,設mini=a[i-1][j].dp-a[i-1][j].x,此時只需在所有的前一周期龍珠的 位置大於後一個周期龍珠的位置中找最小的mini就可以了。
代碼：

#include 
#include 
#include 
#include 
using namespace std;
const int inf=1999999999;
struct node
{
    int x;
    int v;
    int dp;
}a[55][1100];
int bbs(int x)
{
    if(x<0)
    x=-x;
    return x;
}
bool cmp(node l,node r)
{
    return l.x=a[i-1][j].x)
                     {
                         mini=min(mini,(a[i-1][j].dp-a[i-1][j].x));
                         j++;
                     }
                     a[i][k].dp=min(a[i][k].dp,(mini+a[i][k].x+a[i][k].v));
            }
            //前一周期龍珠的位置大於後一個周期龍珠的位置
            j=n;
            mini=inf;
            for(int k=n;k>=1;k--)
            {
                while(j>=1&&a[i-1][j].x>=a[i][k].x)
                {
                    mini=min(mini,(a[i-1][j].dp+a[i-1][j].x));
                    j--;
                }
                a[i][k].dp=min(a[i][k].dp,(mini-a[i][k].x+a[i][k].v));
            }
        }
        int ans=inf;
        for(int i=1;i<=n;i++)
        {
            ans=min(ans,a[m][i].dp);
        }
        printf("%d\n",ans);
    }
    return 0;
}