题目理解

我们有一个 $n \times m$ 的网格，每个格子有一个权值 $v(i,j)$，可正可负。
从 $(1,1)$ 出发，到 $(n,m)$ 结束，每个格子只能访问一次。

关键限制：每天的移动规则：

1. 先选择一个方向（上下左右），走 $0$ 步或任意步（但不能出界）。
2. 再选择一个方向（可与第一步相同或不同），沿着这个方向一直走到边界为止（必须至少走 1 步？题目说“一直走下去，走到地图的某个边界位置”）。

每天结束的位置是第二天的起点，最后一天结束时必须在 $(n,m)$。

目标：最大化经过的格子权值和。

---

移动模式分析

假设某一天起点是 $(x_s, y_s)$：

1. 第一步：选方向 $d_1$，走 $k \ge 0$ 步，到达 $(x_1, y_1)$。
2. 第二步：选方向 $d_2$，沿着这个方向一直走到边界，到达 $(x_e, y_e)$。

注意：第一步可以不走（$k=0$），那么起点就是第一步结束的位置。
第二步必须走到边界，意味着第二步至少走 1 步（除非起点已经在边界上且方向指向边界外，但那样就不动，但这样可能不符合“一直走下去”的意思，一般理解第二步至少走 1 步）。

---

简化理解

这种“两步”结构其实是一种允许中间拐一次弯的路径，并且第二步必须走到边界。
所以一天的路线是：从起点 $(x_s, y_s)$ 到某个中间点 $(x_1, y_1)$（可以等于起点），再沿另一个方向走到边界点 $(x_e, y_e)$。

因为格子不能重复访问，所以每天的路径是简单路径。

---

问题转化

这实际上是一个多段路径规划问题，每一天的路线是一个“L”形或“一”形（如果 $d_1 = d_2$ 就是直线到边界）的路径。

我们可以把问题看成：
从 $(1,1)$ 到 $(n,m)$，路径由若干段这样的“L”形或直线段组成，每段终点在边界上（除了最后一段终点是 $(n,m)$）。

---

动态规划设计

设 $dp[i][j]$ 表示从 $(1,1)$ 走到 $(i,j)$ 的最大权值和。

转移时，我们枚举上一天的起点 $(p,q)$，然后计算从 $(p,q)$ 到 $(i,j)$ 这一天的最大收益。

这一天的路线是：

• 从 $(p,q)$ 先走方向 $d_1$ 若干步（可能 0 步）到 $(a,b)$，
• 再改方向 $d_2$ 一直走到边界，其中 $(i,j)$ 在这条第二步的路径上。

---

更简单的理解

其实第二步必须走到边界，意味着第二步的起点到边界这一段是整行或整列的一段。
所以我们可以枚举第二步的方向和起点，用前缀和快速计算整段的值。

---

高效解法思路

这是一个经典问题（类似“传纸条”的复杂变种），可以用行列前缀和 + DP 解决。

设：

• $row[i][j]$ 表示第 $i$ 行从第 1 列到第 $j$ 列的前缀和。
• $col[i][j]$ 表示第 $j$ 列从第 1 行到第 $i$ 行的前缀和。

定义 $dp[i][j]$：到达 $(i,j)$ 的最大总权值。

转移：

1. 从左边来：$dp[i][j] = \max(dp[i][j], dp[i][k] + (row[i][j] - row[i][k]))$，其中 $k < j$，这表示第二步是向右一直走到 $j$（但 $j$ 不一定是边界，不过题目说第二步必须到边界，所以 $j$ 必须是 $m$ 列？不对，最后一段可能不到边界，因为最后一段终点是 $(n,m)$ 不一定是边界）。
   所以最后一天特殊处理。

2. 从上边来：类似。

实际上更精确的做法是：
我们考虑某一天从 $(x_s, y_s)$ 出发：

• 如果第二步是水平方向，那么整行 $x_s$ 从 $y_s$ 到边界的一段会被走完（如果向右就到 $y=m$，向左就到 $y=1$）。
• 如果第二步是垂直方向，那么整列 $y_s$ 从 $x_s$ 到边界的一段会被走完（如果向下就到 $x=n$，向上就到 $x=1$）。

因此，我们可以预处理每个点向四个方向走到边界的路径权值和，然后做 DP 时，枚举上一天的起点和第二步的方向。

---

算法简述

1. 预处理每个点向四个方向到边界的路径和（用前缀和计算）。
2. 设 $dp[i][j]$ 表示到达 $(i,j)$ 的最大权值和。
3. 转移：
   • 从同一行某个 $k$ 直接走到 $j$（第二步向右）：
     $dp[i][j] = \max(dp[i][j], dp[i][k] + sumRight[i][k])$，其中 $sumRight[i][k]$ 是从 $(i,k)$ 向右走到边界的和。
   • 从同一列某个 $k$ 直接走到 $i$（第二步向下）：
     $dp[i][j] = \max(dp[i][j], dp[k][j] + sumDown[k][j])$。
   • 以及向左、向上的情况类似。
4. 注意不能重复访问，但因为我们 DP 是按行列顺序进行的，所以不会重复（只要第二步是单向延伸）。
5. 最后答案是 $dp[n][m]$。

复杂度 $O(nm(n+m))$ 可能太大（$800^3$ 不行），需要优化。
实际上可以用线段树或单调队列优化到 $O(nm）$。

---

题目核心限制分析

关键限制：每天的移动分为两步：

1. 第一步：选方向走 0 步或任意步
2. 第二步：选方向（可与第一步相同或不同）一直走到边界

这意味着一天的路径是一个“L”形或直线段，且第二步必须延伸到边界。

动态规划状态设计

设 dp[i][j] 表示从 (1,1) 走到 (i,j) 的最大权值和。

转移方程分析

考虑从某个点 (x,y) 转移到 (i,j)，有四种情况：

1. 第二步向右

从 (i,k)（其中 k<j）出发，第二步向右走到边界，经过 (i,j)。

dp[i][j] = max_{k<j} { dp[i][k] + (row_sum[i][j] - row_sum[i][k]) }
         = row_sum[i][j] + max_{k<j} { dp[i][k] - row_sum[i][k] }

这里 row_sum[i][j] 是第 i 行前 j 列的和。

2. 第二步向左

从 (i,k)（其中 k>j）出发，第二步向左走到边界，经过 (i,j)。

dp[i][j] = max_{k>j} { dp[i][k] + (row_sum[i][k] - row_sum[i][j-1]) }
         = -row_sum[i][j-1] + max_{k>j} { dp[i][k] + row_sum[i][k] }

3. 第二步向下

从 (k,j)（其中 k<i）出发，第二步向下走到边界，经过 (i,j)。

dp[i][j] = max_{k<i} { dp[k][j] + (col_sum[i][j] - col_sum[k][j]) }
         = col_sum[i][j] + max_{k<i} { dp[k][j] - col_sum[k][j] }

4. 第二步向上

从 (k,j)（其中 k>i）出发，第二步向上走到边界，经过 (i,j)。

dp[i][j] = max_{k>i} { dp[k][j] + (col_sum[k][j] - col_sum[i-1][j]) }
         = -col_sum[i-1][j] + max_{k>i} { dp[k][j] + col_sum[k][j] }

单调队列优化

观察上述四种转移，都是求形如：

max_{k在某个区间} { dp[...] ± prefix_sum[...] }

对于同一行的转移：

• 向右：固定 i，j 递增，求 max_{k<j} { dp[i][k] - row_sum[i][k] }
• 向左：固定 i，j 递减，求 max_{k>j} { dp[i][k] + row_sum[i][k] }

可以用单调队列维护：

• 向右：维护 dp[i][k] - row_sum[i][k] 的递减队列
• 向左：维护 dp[i][k] + row_sum[i][k] 的递减队列

对于同一列的转移：

• 向下：固定 j，i 递增，求 max_{k<i} { dp[k][j] - col_sum[k][j] }
• 向上：固定 j，i 递减，求 max_{k>i} { dp[k][j] + col_sum[k][j] }

同样用单调队列维护。

算法流程

1. 预处理行列前缀和
2. 初始化 dp[1][1] = v[1][1]
3. 按行处理：
   • 从左到右（向右转移）
   • 从右到左（向左转移）
4. 按列处理：
   • 从上到下（向下转移）
   • 从下到上（向上转移）
5. 每次用单调队列求区间最大值
6. 最终答案 dp[n][m]

复杂度分析

• 每个点被处理常数次
• 单调队列操作 O(1)
• 总复杂度：O(nm)

这种优化方法将原本 O(nm(n+m)) 的复杂度降到了 O(nm)，能够处理 n,m ≤ 800 的数据规模。