时间戳

首页 > 解决方案 > 在少于 O(N*N) 的时间内从城市 1 到达 N 的最短时间

algorithm - 在少于 O(N*N) 的时间内从城市 1 到达 N 的最短时间

问题描述

数组中给出了一些N城市的成本arr[1..N]。j从city到city需要的时间i是|i - j| * arr[i]。条件：现在2 <= N <= 10^5 ， 我们必须找到从 city1 <= arr[i] <= 10^9 到达 city 的最短时间。N1

我可以想到两种方法来解决这个问题：

解决这个问题的一种方法是使用动态规划并计算到达城市的最短j时间2 <= j <= N。终于回来了dp[N]。但这需要O(N*N)时间。

另一种方法是先从 city 到达1city j，2 <= j <= N然后用最短的时间从 city 重复相同的 city j，直到我们到达 city N。但这O(N*N)在最坏的情况下也需要时间。

这个问题有没有更优化的解决方案？

标签： algorithmdata-structuresgraphdynamic-programming

解决方案

让我们专注于您的 DP 方法。

观察：倒退从来都不是最优的。

我们可以使用简单的 DP 在 O(n^2) 中解决它：

DP(i)- 到达城市 i 的最低成本

DP(1) = 0

DP(i) = min 1 <= j < i { DP(j) + arr[j] * (i - j)}- 你决定以某种方式从城市 1 到 j，然后直接跳到城市 i。

让我们稍微改变一下公式：

DP(i) = min 1 <= j < i { ( DP(j) - j * arr[j] ) + i * arr[j] }

我们可以将其视为在特定点评估的最小线性函数：

a_j = arr[j]
b_j = DP(j) - j * arr[j]
x = i

F_j(x) = a_j * x + b_j

我们想找到min 1 <= j < i { F_j(i) }

有一种常见的 DP 优化技巧，称为 Convex Hull Trick。它能够在 O(n log n) 中解决具有这种公式的 DP 问题。您可以在此处找到教程：https ://codeforces.com/blog/entry/63823

推荐阅读