题目重述

我们有一个 $H \times W$ 的网格，要从左上角 $(1,1)$ 走到右下角 $(H,W)$，只能向右或向下走。

• 在第 $i$ 行上走一步（向右）花费 $A_i$ 时间。
• 在第 $j$ 列上走一步（向下）花费 $B_j$ 时间。

求最小总时间。

$H, W$ 最大 $10^5$，直接 DP 会超时。

关键观察

1. 路径的结构

任何一条路径都可以表示为：

• 从 $(1,1)$ 出发，向右走若干步，向下走若干步，交替进行，最终到达 $(H,W)$。
• 假设路径在第 $i_1, i_2, \dots, i_k$ 这些行上向右走了若干段，在列 $j_1, j_2, \dots$ 上向下走若干段。

2. 费用计算

总时间 = 所有行段花费 + 所有列段花费。

具体来说：

• 如果在第 $i$ 行上连续向右走了 $t$ 步，花费 $t \times A_i$。
• 如果在第 $j$ 列上连续向下走了 $s$ 步，花费 $s \times B_j$。

问题转化

我们可以把路径看作一系列决策：
每次选择是换到下一行（花费当前列的 $B_j$）还是换到下一列（花费当前行的 $A_i$）。

更抽象地，这个问题等价于：

• 我们要把 $(H-1)$ 次“向下”和 $(W-1)$ 次“向右”合理安排，使得总花费最小。
• 但花费不是固定的，而是依赖于当前所在的行（向右时）或当前所在的列（向下时）。

核心思路

凸壳优化（斜率优化）

考虑一个更简单的思路：
假设我们知道路径在行 $i_1, i_2, \dots, i_k$ 上向右走，在列 $j_1, j_2, \dots$ 上向下走。

最优路径的性质是：

• 我们只会在 $A_i$ 较小的一些行上向右走较多步。
• 只会在 $B_j$ 较小的一些列上向下走较多步。

事实上，可以证明：最优路径只会经过 $A$ 的前缀最小值行和 $B$ 的前缀最小值列。
换句话说，路径的拐点只出现在 $A$ 或 $B$ 的“极小值”位置。

几何解释

把问题看作在二维平面上：

• 从 $(0,0)$ 到 $(W-1, H-1)$，每步 $(1,0)$ 花费当前 $y$ 对应的 $A_{y+1}$，每步 $(0,1)$ 花费当前 $x$ 对应的 $B_{x+1}$。

那么总花费可以写成： [ \text{cost} = \sum_{i=1}^{H-1} B_{p_i} + \sum_{j=1}^{W-1} A_{q_j} ] 其中 $p_i$ 是路径在列方向上的分布，$q_j$ 是路径在行方向上的分布。

最终算法思想

1. 对 $A$ 数组做单调栈，求出它的前缀最小值序列。
2. 对 $B$ 数组做单调栈，求出它的前缀最小值序列。
3. 用双指针法，在两个序列上“行走”，每次选择当前 $A$ 最小值和 $B$ 最小值中更小的那个方向前进，并累加花费。

这实际上是一个贪心过程：
始终选择当前行花费 $A_i$ 和列花费 $B_j$ 中较小的那个方向走一步，直到到达终点。

为什么贪心正确？

因为如果当前 $A_i < B_j$，那么向右走一步的代价更小，而且不会影响后续向下的代价（因为向下只依赖于列 $B$，与行无关）。反之同理。

这样我们就在 $O(H+W)$ 时间内解决了问题。

总结

这道题的关键是把二维路径问题转化为一维贪心决策：

• 利用“前缀最小值”性质减少候选决策点。
• 通过比较当前行权 $A_i$ 和列权 $B_j$ 决定移动方向。
• 用单调栈预处理，双指针模拟行走过程。