UVa1025

题意理解

https://onlinejudge.org/external/10/1025.pdf

这里要我们求的输出是：最少等待时间。什么是最少等待时间呢？就是在车站逗留的时间。

解题思路

• 用 $d(i, j)$ 表示时刻 i，Mario 在车站 j 最少还需要等待多少时间。
• 边界条件是：$d(T, n) = 0$，表示在 T 时刻，Mario 已经在 n 站台了。其他的 d(T, i) 为正无穷。
• 对于其他的普通的情况，也就是 d(i, j)，可以有 3 种决策：
  • 1、等 1 个时间单位
  • 2、搭乘往右开的车(如果有)
  • 3、搭乘往左开的车(如果有)

代码理解

这里状态转移方程比较直观，其实就是最内层的 for 循环中的处理过程。因为我们的边界条件是 T 时刻，所以，对于时刻 i，我们从 T - 1 开始遍历。

这里一定要明确，$dp[i, j]$ 表示的是时刻 i，在车站 j 最少还需要等待多少时间。

1dp[i][j] = dp[i+1][j] + 1; // 等待一个时间单位

表示，从 dp[i][j] 状态来到 dp[i+1][j]，是在 j 站台等待了一个时间单位。并且，最终来到了 i + 1 时刻。

1dp[i][j] = min(dp[i][j], dp[i+t[j]][j+1]); // 右

表示，从 dp[i][j] 状态来到 dp[i+t[j]][j+1] 状态，是在往右的列车上花费了 t[j] 个时间单位，并且，最终来到了 i + t[j] 时刻和 j + 1 站台。这个过程中，没有等待。

1dp[i][j] = min(dp[i][j], dp[i+t[j-1]][j-1]); // 左

表示，从 dp[i][j] 状态来到 dp[i+t[j-1]][j-1] 状态，是在往左的列车上花费了 t[j-1] 个时间单位(因为题意说，两个站台之间列车往左往右花费的时间是一样的)，并且，最终来到了 i + t[j - 1] 时刻和 j - 1 站台。这个过程中，也没有等待。

注意：这里为什么一次只让列车走一个站台呢？是因为一次走多个站台的情况也被我们这种挨个处理的方式给囊括了，便于我们去处理所有的情况。比如，我想坐列车一次往右走两个站台，那么，其实在我走完一个站台的时候，会有三种决策，那么，其中，直接向右走的决策就和一次走两个站台的那种情况是相等了。