山岳爬升问题需要动态规划。

Question

3

基本上问题是有一系列山峰点，我们只能从一个山峰点移动到下一个更高的山峰点。请参见下面的图像以了解情况。

在上面的图片中，黑色点是山顶，每个山顶都有一些香料和一些味道价值。我们可以从一个山顶移动到另一个山顶品尝其中的香料。

请参见下面的图像以了解有效的移动方式。绿色线条表示有效的移动。

现在，我们将得到一个查询，其中包含2个整数b和c，对于每个查询，我们需要找出是否可以从b山点移动到c山点。如果可以，我们就必须输出旅程的总美味程度。

假设有一个查询，其中b = 1，c = 10。

因此，我们需要找出是否可能从山1到山10移动，如果是，则输出旅程的美味程度。

如果查询很少，问题就很简单，因为对于每个查询，我们只需在循环中迭代并找出是否可以从1到10到达，如果可以，我们将对味道进行求和。

对于这个特定的问题，我们的路径将是1->2->6->7->9->10。

但如果出现查询，例如b=1，c=11。

因此，我们无法从1到11，因此没有路径可行，答案为-1。

但是当有非常大的查询时，我们可以为每个查询迭代循环。我的意思是，我们必须预处理数据，以便在每个查询中我们只需在恒定时间内计算结果。

我特别想知道什么？

如何在恒定时间内知道是否可以从b到c达到。

如果路径可行，则如何在恒定时间内计算路径总和。

- Mr.HITMAN

“_山点系列_”以什么形式出现？是对象数组吗？（能给个例子吗） - Nick Parsons

1

它们将被给定为数组，例如 h[] = {10, 7, 5, 6, 4, 3, 8, 9}，其中 hi 是山峰点的高度。 - Mr.HITMAN

2个回答

1

你可以用 O(nlogn) 的时间复杂度来解决这个问题。

算法

首先找到每座山的下一座更高的山（如果存在）。你可以使用栈在 O(n) 的时间复杂度内完成此操作。
现在，使用二叉上提的最近公共祖先或稀疏表，在第一步中找到的下一座更高的山创建一棵树，并检查是否存在从 a 到 b 的路径。如果 LCA(a,b) = c，则存在从 a 到 b 的路径，时间复杂度为 O(logn) 或 O(1)。
要计算路径总和，您需要存储从根节点到树节点的每个高度的总和。这也可以使用 DFS 或 BFS 在 O(n) 的时间复杂度内完成。
最后，即使在最坏的情况下，整个程序也将在 O(nlogn) 的时间复杂度内运行。

- captainLevi

谢谢，我已经完成了这个问题，但是我很感激你的努力。 - Mr.HITMAN

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

你可以使用最近公共祖先算法解决此问题，使用O(n)的空间和O(n+q)的时间，其中q是查询数量。这里有一个Topcoder算法教程来解释该算法。

为了将问题转换成这种形式，为每个山定义一个节点，并将父节点设置为我们可以从此点移动到的山。引入一个额外的根节点，它是没有有效移动的山的父节点。

然后要确定是否存在从b到c的路径，只需检查LCA(b,c)是否等于c即可。

您还可以预先计算出以每个节点为起点，以根节点为终点的路径上香料总数，使用O(n)的时间复杂度。为了计算路径上的香料总数，只需从以c为起点的总数中减去以b为起点的总数即可。

一开始构建图可能有些困难，但也可以使用下一个更大元素算法以O(n)的时间来完成。