看成同时从左上开始传两个纸条，用f(i,j,k)表示这一步的横纵坐标之和为i，第一张纸条纵坐标为j，第二张纸条纵坐标为k（因为路径不重合，所以j≠k，不妨令j<k）。可以看出每走一步纸条的横纵坐标之和都会加一，所以i其实就是传递的次数+2.

每个状态可以由以下4种情况转移而来：

1. 第一张纸条由上面，第二张纸条由上面 f(i,j,k)=max{f(i,j,k),f(i-1,j-1,k-1)+a[j][i-j]+a[k][i-k]}

2. 第一张纸条由上面，第二张纸条由左边 f(i,j,k)=max{f(i,j,k),f(i-1,j-1,k)+a[j][i-j]+a[k][i-k]}

3. 第一张纸条由左边，第二张纸条由上面 f(i,j,k)=max{f(i,j,k),f(i-1,j,k-1)+a[j][i-j]+a[k][i-k]}

4. 第一张纸条由左边，第二张纸条由左边 f(i,j,k)=max{f(i,j,k),f(i-1,j,k)+a[j][i-j]+a[k][i-k]}

可以看出，每种转移都是在一定情况下才能发生的（没有越界，而且纸条没有重合）。由于一开始数组中都是0，不进行越界判断也无妨，但是纸条重合的判断必须有，即只有k-1>j时才能由第3种情况转移.

然后重点来了

本题解和前4页题解（没往后面翻了orz）的不同之处在于，用了滚动数组。其实就是因为转移时只会由f(i-1,x,y)转移而来，在数组中省去了i这一维，节约了一些空间。需要注意的就是由于状态都是由更小的j和/或k转移而来，j和k都需要倒序枚举，防止状态在转移之前被修改。

代码如下：

#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

/*
这一部分是用来方便地转换标准io和文件io，
只需在#include <iostream>前加上//就可以转换为文件io
*/

#ifndef _GLIBCXX_IOSTREAM //这个在iostream头文件中define了，这句话的意思就是如果没有#include <iostream>则执行下面的语句
ifstream cin("0.in");
ofstream cout("0.out");
#endif

int n,m,f[210][210],a[210][210];

int main()
{
    int i,j,k;
    
    cin>>n>>m;
    
    for (i=1;i<=n;++i)
    {
        for (j=1;j<=m;++j)
        {
            cin>>a[i][j];
        }
    }
    
    f[1][2]=a[1][2]+a[2][1];
    
    for (i=4;i<n+m;++i)
    {
        for (j=min(i-2,n);j>=1;--j) //注意要倒序枚举j和k
        {
            for (k=min(i-1,n);k>j;--k)
            {
                if (j>1)  //这里的条件判断貌似是不需要的，但我觉得加上更好
                {
                    f[j][k]=max(f[j][k],f[j-1][k]);
                }
                if (j>1&&k>1)
                {
                    f[j][k]=max(f[j][k],f[j-1][k-1]);
                }
                if (k-1>j)
                {
                    f[j][k]=max(f[j][k],f[j][k-1]);
                }
                f[j][k]+=a[j][i-j]+a[k][i-k];
            }
        }
    }
    
    cout<<f[n-1][n];
    
    return 0;
}