hdu 3440 House Man（差分限制）

House Man

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2471    Accepted Submission(s): 1007

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  

題意：

有N個在一條直線上的房子, 每個房子有着不同的高度, 一個超人可以将這些房子左右移動

但不能改變房子之間的相對位置.

現在超人要從最矮的房子跳到剛好比他高的房子上面, 且每次跳的房子都要比目前房子要高.

那麼最後超人肯定會跳到最高的房子上面, 現在給出超人能夠跳的最遠距離, 問: 如何擺放

這些房子, 使得超人能夠經過所有的房子跳到最高的房子, 又要使最矮的房子和最高的房子

之間的距離最遠??      

思路：此題其實不難，不過跟一般的差分限制的差別在于一般的差分限制都是排隊模型，也就是從一段到另一端的關系

而此題有可能來回跳，中間會出現一個|a[i+1].id-a[i].id|<=D

此時出現了絕對值怎麼辦呢？

注意差分限制的起點和終點必須按照從小到大的順序，因為邊都是有向邊

我們約定有向邊都是從編号小的到編号大的，然後我們最後起點和終點也換成從編号小的找編号大的即可

注意INF要大于1000000000

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define N 1050
#define INF 1000000009
struct Edge
{
    int v,next,w;
} edge[N*N];
struct Node
{
    int id,v;
} p[N];
int cnt,head[N],n;
int d[N],vis[N],num[N];
void init()
{
    cnt=0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int spfa(int s,int t)
{
    memset(vis,0,sizeof(vis));
    memset(num,0,sizeof(num));
    for(int i=1; i<=n; i++)
        d[i]=i==s?0:INF;
    vis[s]=1;
    queue<int>que;
    que.push(s);
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=0;
        num[u]++;
        if(num[u]>n) return -1;
        for(int i=head[u]; i!=-1; i=edge[i].next)
        {
            int v=edge[i].v,w=edge[i].w;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                if(!vis[v])
                {
                    vis[v]=1;
                    que.push(v);
                }
            }
        }
    }
    return d[t];
}
bool cmp(Node a,Node b)
{
    return a.v<b.v;
}
int main()
{
    int T,q=1;
    int s,t,w,dis;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d %d",&n,&dis);
        int s,t,maxn=-INF,minn=INF;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&p[i].v);
            p[i].id=i;
            if(p[i].v<minn)
            {
                minn=p[i].v;
                s=i;
            }
            if(p[i].v>maxn)
            {
                maxn=p[i].v;
                t=i;
            }
        }
        for(int i=2; i<=n; i++)
            addedge(i,i-1,-1);
        sort(p+1,p+1+n,cmp);
        for(int i=2; i<=n; i++)
        {
            if(p[i].id>p[i-1].id)
                addedge(p[i-1].id,p[i].id,dis);
            else
                addedge(p[i].id,p[i-1].id,dis);
        }
        if(s>t) swap(s,t);
        printf("Case %d: ",q++);
        printf("%d\n",spfa(s,t));
    }
    return 0;
}