很显然这是一道dp（只能右或下，无后效性）。那么一起来分析吧！ 首先倒过来想，一条路径正走和反走，它们的和都是一样的。所以我们可以把题意改成： 从左上到右下，走两条路径，不能相交（班里每个同学只会帮他们一次），只能右走或下走，求两条路径最大和。 这样，状态设置就可以直接参考这题（acgo）或这题（洛谷）了。状态转移方程也是类似的，fi,j,k,l=max(fi−1,j,k−1,l,fi−1,j,k,l−1,fi,j−1,k−1,l,fi,j−1,k,l−1)+ai,j+ak,lf_{i,j,k,l}=max(f_{i-1,j,k-1,l},f_{i-1,j,k,l-1}, f_{i,j-1,k-1,l},f_{i,j-1,k,l-1})+a_{i,j}+a_{k,l}fi,j,k,l =max(fi−1,j,k−1,l ,fi−1,j,k,l−1 ,fi,j−1,k−1,l ,fi,j−1,k,l−1 )+ai,j +ak,l 。但是，两条路径不能相交怎么搞？很简单，把 lll 的范围设置为 j+1≤l≤nj+1 \leq l \leq nj+1≤l≤n 就行了。这样子，第二条路径一定在第一条路径的右上方。 注意，最后的结果应该是 fm,n−1,m−1,nf_{m,n-1,m-1,n}fm,n−1,m−1,n ，因为 lll 是从 j+1j+1j+1 开始扫的，fm,n,m,nf_{m,n,m,n}fm,n,m,n 无意义。又因为第二条路径一定在第一条路径的右上方，所以第一条路径一定传给右下角的人左边，第一条路径一定传给右下角的人上边，那么就可以把 fm,n−1,m−1,nf_{m,n-1,m-1,n}fm,n−1,m−1,n 作为结果。 时空复杂度均为 O(n4)O(n^4)O(n4)，可过。 本题 f 数组可以用滚动数组压掉一维，空间复杂度变成 O(n^3)，不过不搞也不会MLE 温馨提示：不要复制哟。FZ，HGZF