213C

考虑朴素 DP。定义 $f_{i,j,i2,j2}$ 表示两个人分别在 $(i,j),(i2,j2)$ 时获得的最大收益。复杂度 $O(n^4)$，不行。 我们换种方法，定义 $f_{st,x,y}$ 表示两人同时走了 $st$ 步，分别向右走了 $x,y$ 步。显然如果向右的步数确定了，向下的也确 ......

Relay Race - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 本题是棋盘dp的经典例题。 可以先转化一下题意：从(1,1)走两条路径到(n,n)，再确保两人是同步行走的。 我们可以让一人的走路范围一直在左下方向，一人的走路范围一直在右上方向。（倘若两人的路径交叉，则都可以转 ......