P7074 [CSP - J 2020] 方格取数

对于每一列，我们可以：

1. 从左边过来，然后向上走

2. 从左边过来，然后向下走

3. 从上面下来

4. 从下面上来

我们可以考虑两种方向：

1. 从上往下走 2. 从下往上走

我们可以用两个 DP 数组：

d[i][j]：到达 $(i,j)$ 时，路径方向是向下的最大和

u[i][j]：到达 $(i,j)$ 时，路径方向是向上的最大和

状态转移：

对于d[i][j]：

1.可以从左边过来：d[i][j-1] + a[i][j] 或 u[i][j-1] + a[i][j]

2.可以从上面下来：d[i-1][j] + a[i][j]

对于u[i][j]：

3.可以从左边过来：d[i][j-1] + a[i][j] 或 u[i][j-1] + a[i][j]

4.可以从下面上来：u[i+1][j] + a[i][j]

代码

点我查看

AC记录