首页 > ACM题库 > HDU-杭电 > HDU 3440-House Man-最短路径-[解题报告]HOJ
2014
03-23

HDU 3440-House Man-最短路径-[解题报告]HOJ

House Man

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

3
4 4 
20 30 10 40 
5 6 
20 34 54 10 15 
4 2 
10 20 16 13 

样例输出:

Case 1: 3
Case 2: 3
Case 3: -1

比较好的一道差分约束的题目。

差分约束里面,我觉得最经典的两句话就是 按最短路求的值达到可能的最大,按最长路求的值达到可能的最小。

建图,比较简单,每个点dis[i+1]>=dis[i]+1 所以i+1->i 连条-1的边。

其次 排序 高度数组,保存对应的id,然后遍历,相邻两个,连条d的边。

超时了几次,原因是,连长度为d的边,对于下标小的点,往下标大的点连条边就行,不需要反过来再连。

wa了一次、、、汗、、inf开小了、、最大可能dis=1000*1000000=10^9,我设了10^8,汗~~

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
int T,n,d,dis[1010],nxt[1010],h,in[1010],cnt[1010];
const int inf=1000000000;
using namespace std;
struct node
{
	int id,h;
	node(int a=0,int b=0):id(a),h(b){}
	friend bool operator < (node a,node b)
	{
		return a.h<b.h;
	}
};
struct edge
{
	int y,l;
	edge(int a,int b):y(a),l(b){}
};
vector<edge>vt[1010];
node a[1010];
int spfa(int x,int y)
{
	fill(dis,dis+1+n,inf);
	memset(in,0,sizeof(in));
	dis[x]=0;
	in[x]=1;
	memset(cnt,0,sizeof(cnt));
	cnt[x]=1;
	queue<int>q;
	q.push(x);
	while(!q.empty())
	{
		int s=q.front();
		q.pop();
		in[s]=0;
		for(int i=0;i<vt[s].size();i++)
		{
			int y=vt[s][i].y,l=vt[s][i].l;
			if(dis[y]>dis[s]+l)
			{
				dis[y]=dis[s]+l;
				if(!in[y])
				{
					q.push(y);
					cnt[y]++;
					if(cnt[y]>n)return -1;
					in[y]=1;
				}
			}
		}
	}
	return dis[y];
}
int main()
{
	scanf("%d",&T);
	for(int cas=1;cas<=T;cas++)
	{	
		scanf("%d%d",&n,&d);
		for(int i=1;i<=n;i++)
			vt[i].clear();
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&h);
			a[i]=node(i,h);
		}
		sort(a+1,a+1+n);
		for(int i=1;i<n;i++)
		{
			vt[i+1].push_back(edge(i,-1));
		}
		for(int i=1;i<n;i++)
		{
			vt[min(a[i+1].id,a[i].id)].push_back(edge(max(a[i+1].id,a[i].id),d));
		}
		int a1=a[1].id,a2=a[n].id,k;
		if(a1<a2)
		{
			k=spfa(a1,a2);
		}
		else
		{
			k=spfa(a2,a1);
		}
		printf("Case %d: %d\n",cas,k);
	}
	return 0;
}

参考:http://blog.csdn.net/nash142857/article/details/8259753


  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  2. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。