Working Out

翻译(口胡)

有一个n*m大小的健身房，每走到一个点(i,j)，都会消耗a[i][j]大小的卡路里，小西从(1,1)出发走到(n,m)，只

能向右走或向下走，小瓜从(n,1)出发走到(1,m),只能向右走或向上走,他们两人决定在某一个点会面且只进行一次

会面，那个点的卡路里不计入总卡路里。求出小西和小瓜可以消耗的最大总卡路里值。并且他们健身的速度不

同，即假设小西走了5步，小瓜可能只走了一步

分析

因为他们要会面，所以我们可以针对每个点。即如果在这个点会面，能消耗最多的卡路里。但是之后不能再会面

并且还要从这个点出发，那么我们可以定义四个方向——左上到右下，左下到右上，右上到左下，右下到左上。

也就是说，我们要分这两种情况讨论

代码

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#define R register
#define ll long long
#define inf INT_MAX
using namespace std;
const int N=1e3+10;
int n,m;
ll x[N][N];
ll a[N][N],b[N][N],c[N][N],d[N][N];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
        scanf("%lld",&x[i][j]);
//左上到右下 
for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
        a[i][j]=max(a[i-1][j],a[i][j-1])+x[i][j];

//左下到右上 
for (int i=n;i>=1;i--)
    for (int j=1;j<=m;j++)
        b[i][j]=max(b[i+1][j],b[i][j-1])+x[i][j];

//右上到左下
for (int i=1;i<=n;i++)
    for (int j=m;j>=1;j--)
        c[i][j]=max(c[i-1][j],c[i][j+1])+x[i][j];

//右下到左上
for (int i=n;i>=1;i--)
    for (int j=m;j>=1;j--)
        d[i][j]=max(d[i+1][j],d[i][j+1])+x[i][j];

//枚举每个点 
ll ans=0;
for (int i=2;i<n;i++)
    for (int j=2;j<m;j++)
    {
        ans=max(ans,a[i-1][j]+d[i+1][j]+b[i][j-1]+c[i][j+1]);
        ans=max(ans,a[i][j-1]+d[i][j+1]+b[i+1][j]+c[i-1][j]);
    }

printf("%lld\n",ans);

return 0;
}