题解

考虑某一个点(i, j)，可能从上边(i-1, j)、下边(i+1, j)、左边(i, j-1)转移过来，i既可以从i-1递推，也可以由i+1递推，这样一来就无法通过一轮遍历递推出来，必然需要正向、反向两次递推！

那么，在定义状态的时候，就需要考虑方向这个因素。

状态定义：

设a[][]表示方格的数

设f[i][j][0]表示从起点(1, 1)到(i, j)，且最后一次是从上边转移的所有数之和最大值

设f[i][j][1]表示从起点(1, 1)到(i, j)，且最后一次是从下边转移的所有数之和最大值

设f[i][j][2]表示从起点(1, 1)到(i, j)，且最后一次是从左边转移的所有数之和最大值

状态转移：

有三种转移方式：

f[i][j][0] = max(f[i-1][j][0], f[i-1][j][2]) + a[i][j]

f[i][j][1] = max(f[i+1][j][1], f[i+1][j][2]) +a[i][j]

f[i][j][2] = max(f[i][j-1][0], max(f[i][j-1][1], f[i][j-1][2])) +a[i][j]

由于i既可以依赖i-1，又可以依赖i+1，因此需要两次递推

第一次从左到右、从上到下遍历递推，计算f[i][j][0], f[i][j][1]

第二次从左到右、从下到下遍历递推，计算f[i][j][1], f[i][j][2]

需要注意下标不能超出棋盘范围

初始化：

f[1][1][0] = f[1][1][1] = f[1][1][2] = a[1][1]

结果：

max(f[n][m][0], f[n][m][2])

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int n, m;
int a[N][N];
long long f[N][N][3];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];
    
    memset(f, -0x3f, sizeof(f));

    f[1][1][0] = f[1][1][1] = f[1][1][2] = a[1][1];
    for(int j = 1; j <= m; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            if(i - 1 >= 1) f[i][j][0] = max(f[i-1][j][0], f[i-1][j][2]) + a[i][j];
            if(j - 1 >= 1) f[i][j][2] = max(f[i][j-1][0], max(f[i][j-1][1], f[i][j-1][2])) + a[i][j];
        }
        for(int i = n; i >= 1; i--)
        {
            if(i + 1 <= n) f[i][j][1] = max(f[i+1][j][1], f[i+1][j][2]) + a[i][j];
            if(j - 1 >= 1) f[i][j][2] = max(f[i][j-1][0], max(f[i][j-1][1], f[i][j-1][2])) + a[i][j];
        }
    }
           
    cout << max(f[n][m][0], f[n][m][2]);

    return 0;
}

蛟龙突击队