HDU3440 House Man

House Man

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2056 Accepted Submission(s): 811

Problem Description

In Fuzhou, there is a crazy super man. He can’t fly, but he could jump from housetop to housetop. Today he plans to use N houses to hone his house hopping skills. He will start at the shortest house and make N-1 jumps, with each jump taking him to a taller house than the one he is jumping from. When finished, he will have been on every house exactly once, traversing them in increasing order of height, and ending up on the tallest house.

The man can travel for at most a certain horizontal distance D in a single jump. To make this as much fun as possible, the crazy man want to maximize the distance between the positions of the shortest house and the tallest house.

The crazy super man have an ability—move houses. So he is going to move the houses subject to the following constraints:

1. All houses are to be moved along a one-dimensional path.

2. Houses must be moved at integer locations along the path, with no two houses at the same location.

3. Houses must be arranged so their moved ordering from left to right is the same as their ordering in the input. They must NOT be sorted by height, or reordered in any way. They must be kept in their stated order.

4. The super man can only jump so far, so every house must be moved close enough to the next taller house. Specifically, they must be no further than D apart on the ground (the difference in their heights doesn't matter).

Given N houses, in a specified order, each with a distinct integer height, help the super man figure out the maximum possible distance they can put between the shortest house and the tallest house, and be able to use the houses for training.

Input

In the first line there is an integer T, indicates the number of test cases.(T<=500)

Each test case begins with a line containing two integers N (1 ≤ N ≤ 1000) and D (1 ≤ D ≤1000000). The next line contains N integer, giving the heights of the N houses, in the order that they should be moved. Within a test case, all heights will be unique.

Output

For each test case , output “Case %d: “first where d is the case number counted from one, then output a single integer representing the maximum distance between the shortest and tallest house, subject to the constraints above, or -1 if it is impossible to lay out the houses. Do not print any blank lines between answers.

Sample Input

3

4 4

20 30 10 40

5 6

20 34 54 10 15

4 2

10 20 16 13

Sample Output

Case 1: 3

Case 2: 3

Case 3: -1

Author

jyd

Source

2010 ACM-ICPC Multi-University Training Contest（1）——Host by FZU

題意：一個人從一個樓頂跳去另一個樓頂，他隻能從低的往高的跳，最初在最低的房子，要跳到最高的房子，房子可以水準移動，但是房子的相對位置不能變化，問最低的房子和最高的房子最遠是多少。

因為每個房子都要到達，是以他跳的順序一定是确定的，是以很容易可以寫出關系 |現在的位置-下一個要跳到的位置|<=他最遠能跳的距離D。

加一個限制條件把這個絕對值去掉，每次都是從一個序号小的跳到序号大的是以就是d[v]-d[u]<=D，u的序号比v小，然後建圖的時候就可以判斷兩個房子能不能可達（兩個房子之間的距離小于D可達），每個點的坐标不能相同，是以就是d[i+1]-d[i]>=1,變一下就是d[i]-d[i+1]<=-1，然後取出最小高度和最大高度的序号，比較下取小的，從小的開始跑一遍spfa（建圖序号都是從小的跑到大的）。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int MAXN=1010;
const int MAXE=2010;
const int INF=1<<30;
int head[MAXN],size=0;
struct EDGE
{
    int v,next;
    int dis;
}edge[MAXE];
struct height
{
    int hei,id;
}h[MAXN];
bool cmp(height x,height y)
{
    return x.hei<y.hei;
}
void init()
{
    memset(head,-1,sizeof(head));
    size=0;
}
void add_edge(int u,int v,int dis)
{
    edge[size].v=v;
    edge[size].dis=dis;
    edge[size].next=head[u];
    head[u]=size++;
}
int dis[MAXN],cnt[MAXN],n;
bool vis[MAXN];
bool spfa(int s)
{
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    vis[s]=1;
    dis[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(dis[v]>dis[u]+edge[i].dis)
            {
                dis[v]=dis[u]+edge[i].dis;
                if(!vis[v])
                {
                    vis[v]=1;
                    cnt[v]++;
                    if(cnt[v]>n)
                        return 0;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}
int w;
bool build()
{
    int i;
    for(i=1;i<n;i++)
    {
        add_edge(i+1,i,-1);
        int u=min(h[i].id,h[i+1].id);
        int v=max(h[i].id,h[i+1].id);
        int d=abs(h[i+1].id-h[i].id);
        if(d>w)
            return 0;
        add_edge(u,v,w);
    }
    return 1;
}
int main()
{
    int t,i,flag=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&w);
        init();
        for(i=1;i<=n;i++)
        {
            scanf("%d",&h[i].hei);
            h[i].id=i;
        }
        sort(h+1,h+1+n,cmp);
        printf("Case %d: ",flag++);
        if(!build())
        {
            printf("-1\n");
            continue;
        }
        int u=min(h[1].id,h[n].id);
        int v=max(h[1].id,h[n].id);
        if(spfa(u))
        {
            printf("%d\n",dis[v]);
        }
        else
            printf("-1\n");
    }
    return 0;
}