寻找最佳路径（如果存在）

Question

给定参数k和数组[a₀,a₁, a₂, a₃, ..., a_n]，其中 a_x 定义了地形的高度，找到使地形可通行所需的最少工作量。如果两个相邻地方之间的差异小于或等于k，则该地形是可以通过的。 a_x 处的地形高度可以更改，所需的工作量等于您所做的高度差。 a₀ 和 a_n 的高度无法更改，因此某些地形可能会完全无法通过。

我已经为此苦苦挣扎了一段时间：这是我到目前为止的想法：当然，找到解决方案（不考虑最少的工作量）很容易 - make 'steps' 从 a₀ 到 a_n k = 2 的图表（红点是旧地形的高度，灰色是新地形的高度）。

（此特定地形的输入为：k = 2, [0, 2, 3, 2, 5, 4, 5, 7]）

如您所见，新地形没有考虑旧地形，因此将旧地形转换为新地形所需的工作量可能很大。

确定路径是否存在很简单：k >= |a₀-a_n|/n，但我没有关于我将如何寻找最佳解决方案的想法。

Answer 1

一个暴力解决方案是这样的对于每个元素，考虑三个下一个状态，其中一个状态为 h + 1、h + 0、h - 1，其中 h 是元素的高度。现在继续遍历数组，看到以下几点 1）如果状态已经到达较早丢弃它（所以为此制作位掩码dp）

2)如果你到达一个状态，其中遍历的相邻元素差异不是k，则丢弃它。

3)如果到现在为止完成的总工作量大于找到之前的最小工作量，则丢弃它。

Answer 2

使用单纯形法求解下列线性规划。

minimize sum_i y_i
subject to
# y_i is notionally |x_i - a_i|
# equality holds in every optimal solution
y_i >= x_i - a_i for all i
y_i >= a_i - x_i for all i
# transformed terrain is passable, i.e., |x_i - x_{i+1}| <= k
x_i - x_{i+1} <= k for all i
x_{i+1} - x_i <= k for all i

Answer 3

设 ht = an-a0 为总高度。让 hAverageStep = ht/n。 k是最大步长。

理想情况下，在第 'i' 步，高度差应为 i*hAverageStep。在这种情况下，路径只是一条恒定的直线。我们想更接近这条直线。

对于步骤'i'，您可以观察是否需要在这一点"work"将其移动到直线上。如果该工作大于 k，则您还必须移动其他点，例如您以前工作不够的一些点。

如果将每个点移动到需要的程度后仍未达到 'an'，则无解。

寻找最佳路径（如果存在）

Finding optimal path (if exists)

arrays

algorithm

computer-science