本文主要是介绍Mountain climbing，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem Description
又这是一个关于登山的问题。现有n座山位于一条直线上，每座山可以看成一条垂直于地面的线段，一端点在地面上，
这些山编号从左往右为1到n，第i座山位于xi高为hi。
对于任意的两座山a和b，如果a的顶端能看见b的顶端，则他们可以用绳索连接。a能看见b，当且仅当他们顶端的连线
不能穿过其他山或者触摸到其他山。若a与b能用绳索连接那么登山者可以用一个单位的时间从a到b或者从b到a
（不论绳索多长,且只能从左边往右边）。
现在我们的目的地第n座山，现在要你求出每座山到达第n座山要需要的最短时间。
Input
输入第一行为一个正整数T(1<= T < =20)，表示有T组数据。
每组数据：
第一行一个整数n（1<=n<=100 000）表示一共n座山。
接下去n行每行两个数xi， hi。 (0<xi,hi<=10^8)
数据保证输入的xi（X1<...<Xi-1<Xi<Xi+1<...<Xn）.
Output
对于每个询问，先输出“Case#i: ”,i表示第i组数据，接着输出n个整数，第i个数表示从第i座山出发最少要花费多少时间能到达目的地。
Sample Input
1
5
1 5
2 1
3 2
4 3
5 4
Sample Output
Case#1: 1 3 2 1 0
/*
解题报告：三个点 A(x1,y1),B(x2,y2),C(x3,y3);
判断线段AB与点C的关系:
1.(x1-x2)*(y3-y2)-(y1-y2)*(x3-x2)>0(则C在线段AB的上方)
2.(x1-x2)*(y3-y2)-(y1-y2)*(x3-x2) < 0 (则C在线段AB的下方)
3.(x1-x2)*(y3-y2)-(y1-y2)*(x3-x2) == 0 (则C在线段AB上)
*/
//标程：
#include <iostream> #include <cstdio>
#include <cstring>
using namespace std;
class point
{
public:
__int64 x;
__int64 y;
}p[100010];
int dp[100010]; // 记录dp[i]到dp[n]的步数；
int next[100010]; // 记录当前点与下一个相连的点；
int judge(point p0, point p2, point p1){
__int64 c= (p0.x - p1.x)*(p2.y-p1.y)-(p0.y - p1.y)*(p2.x-p1.x);
if(c>=0) return 0;
else return 1;
}
int main()
{
freopen("a.txt","r",stdin);
int t, n, i;
scanf("%d",&t);
int k = 0;
while(t--)
{
k++;
scanf("%d",&n);
for(i = 1; i <= n; i ++)
scanf("%I64d%I64d",&p[i].x,&p[i].y);
memset(next,0,sizeof(next));
dp[n] = 0;
dp[n-1] = 1;
next[n-1] = n;
for(i = n-2; i > 0; i --)
{
int temp = i + 1;
while(temp != n && judge(p[next[temp]],p[temp],p[i]))
{// 如果judge函数return 1，则 点i 和 点next[temp]可以直接相连；
temp = next[temp];
}
next[i] = temp;
dp[i] = dp[temp] + 1;
}
printf("Case#%d:",k);
for(i = 1; i <= n; i ++)
printf(" %d",dp[i]);
printf("\n");
}
return 0;
}
这篇关于Mountain climbing的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
