爬坡问题需要动态编程 [英] Hill climbing problem requiring Dynamic programming

问题描述

因此，基本上，问题是有一系列山丘点.我们只能从一个山点移动到下一个更大的山点.

请查看下图以了解想法.

在上面的图像中，黑点是山顶，每个山顶上都有一些带有一定口味价值的香料.我们可以从一个山顶移到另一个山顶，品尝其中的香料.

请参阅下图以了解有效的移动.绿线给出有效的移动.

因此，现在我们将得到一个包含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的持续时间是否有可能.

如果路径是可行的，而不是如何在恒定时间内计算路径的总和.

解决方案

您可以使用O(n)空间和O(n + q)时间来解决此问题，其中q是使用最低公共祖先算法的查询数.这是一个 topcoder算法教程，介绍了算法.

要将问题转换为这种形式，请为每个山峰定义一个节点，然后让节点的父节点成为我们可以从此处移动到的山峰.引入一个额外的根节点，该节点是没有有效移动的任何山丘的父级.

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

您还可以在O(n)中预先计算从每个节点开始到根节点的路径上的香料总和.要计算沿路径的总和，只需从b开始的总和中减去c开始的总和.

一开始似乎很难构建图形，但是也可以使用 解决方案

You can solve this with O(n) space and O(n+q) time where q is the number of queries using a lowest common ancestor algorithm. Here is a topcoder algorithm tutorial that explains the algorithm.

To convert the problem into this form, define a node for each hill, and let the parent of a node be the hill we can move to from this point. Introduce one extra root node that is the parent of any hills that have no valid move.

Then to determine if there is a path from b to c, you simply check whether LCA(b,c) is equal to c.

You can also precompute in O(n) the sum of spices on a path starting at each node and ending at the root node. To compute the sum along a path, you simply subtract the sum starting at c from the sum starting at b.

It may seem a bit hard to construct the graph in the first place, but this can also be done in O(n) using a next greater element algorithm.

这篇关于爬坡问题需要动态编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！