题意： 给定 n×m 方格图，每个格子上有个权值 ai,j（可能负数）。从左上角 (1,1) 走到右下角 (n,m)，一步可以向上，下，右的其中一个方向移动一格。把路径上的所有格子的权值加起来得到路径的权值。求最大的路径的权值。不能重复踏入一个格子两次。

Data range：|ai,j|≤104,n,m≤103。

分析： 记忆化确实有点妙，考场上被 T3 恶心（指没读题）后秒出了最难的解法然后写完跑路。

考虑大力 dp，设 f(i,j) 为走到 (i,j) 可能的最大权值。

然后发现可以一列一列转移，对于 f(i,j) 考虑其从 f(k,j−1) 转移而来。不妨设 k≤i 那么这一列的贡献就是第 j−1 列上 [k,i] 位置的值，是一个前缀和的形式。

然后发现前缀和里 sumj,i 是不变的，只需要维护前面 f(k,j−1)−sumj,k 的最大值就可以了。复杂度 O(nm)。其实 dp 和记忆化都是利用了一个位置不能走两次的约束。

听说这题和 2019 一样又是抄了 USACO ？