2020-06-01 递纸条

//
//  main.cpp
//  洛谷
//
//  Created by Jalor on 2020/5/26.
//  Copyright © 2020 Jalor. All rights reserved.
//

#include <iostream>
#include <cstdio>
#define maxn 55
using namespace std;

int f[maxn][maxn][maxn][maxn];//状态转移
int mp[maxn][maxn];//地图
int n,m;

//四数比较
int max_ele(int a,int b,int c,int d){
    if (b>a)
        a = b;
    if (c>a)
        a = c;
    if (d>a)
        a = d;
    return a;
}

int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            scanf("%d",&mp[i][j]);
    //状态转移
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            for (int k=1;k<=n;k++)
                //l从j+1开始是因为预防重合
                for (int l=j+1;l<=m;l++) f[i][j][k][l] = max_ele(f[i][j-1][k-1][l],
                                                                 f[i-1][j][k][l-1],
                                                                 f[i][j-1][k][l-1],
                                                                 f[i-1][j][k-1][l])
                    +mp[i][j]+mp[k][l];
    
    printf("%d\n", f[n][m-1][n-1][m]);
    return 0;
}