本人比较菜。。。费用流什么的都不会， 以前用四重循环做的， 在书上看见了三重循环的做法， 打了打发现比较难搞， 想看看题解发现大佬们都和书上的不太一样， 无奈硬着头皮调过去了。。。。结果发现速度飞快， 洛谷上原来四重循环715ms，现在67ms就过了。。。。

一些易错的细节在代码里。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<cmath>
#include<cstdlib>
#include<ctime>

using namespace std;

#define FOR(a, b, c) for(int a = b; a <= c; a++)

const int mx = 1e5 + 5;
const int inf = 1<<30;

void fre() {
    freopen(".txt", "r", stdin);
    freopen(".txt", "w", stdout);
}

int c[55][55];
int n, m;
int f[222][55][55];

int main(){
    //fre();
    cin >> n >> m;
    FOR(i, 1, n) FOR(j, 1, m) scanf("%d", &c[i][j]);

    f[0][1][1] = c[1][1];
    FOR(i, 0, n+m-3) 
        FOR(x1, 1, min(i+2, n)) //这里x的上界一定要限制， 不然y会变成负数， 但不知为何竟然没有RE， 洛谷能拿90分。。。WA了一个点。。。 
            FOR(x2, 1, min(i+2, n)) {//这个错找了20多分钟。。。。求解答为什么不会RE。。。 
                int y1 = i+2-x1, y2 = i+2-x2;
                int F = f[i][x1][x2];
                //需要枚举四个决策， 因为是顺推， 加的是下一个位置的值， 因此要知道下一个位置是否重叠， 如下。
                //本人比较菜， 只会朴素枚举。。。 
                // R: move right  D: move down 
                //both R && both D
                if(x1 == x2) 
                f[i+1][x1][x2] = max(f[i+1][x1][x2], F + c[x1][y1+1]),
                f[i+1][x1+1][x2+1] = max(f[i+1][x1+1][x2+1], F + c[x1+1][y1]);
                else 
                f[i+1][x1][x2] = max(f[i+1][x1][x2], F + c[x1][y1+1] + c[x2][y2+1]),
                f[i+1][x1+1][x2+1] = max(f[i+1][x1+1][x2+1], F + c[x1+1][y1] + c[x2+1][y2]);
                //这里注意的是
                // x1+y1 == x2 + y2 因此如果 y1+1 == y2, 则 x1 == x2+1, 只需判断一个就行 
                // 1 R 2 D
                if(y1+1 == y2) f[i+1][x1][x2+1] = max(f[i+1][x1][x2+1], F + c[x1][y1+1]);
                else f[i+1][x1][x2+1] = max(f[i+1][x1][x2+1], F + c[x1][y1+1] + c[x2+1][y2]);
                // 1 D 2 R
                if(y1 == y2+1) f[i+1][x1+1][x2] = max(f[i+1][x1+1][x2], F + c[x1+1][y1]);
                else f[i+1][x1+1][x2] = max(f[i+1][x1+1][x2], F + c[x1+1][y1] + c[x2][y2+1]);
            }

    cout << f[n+m-2][n][n];
    return 0;
}