首先这个人呢,

根据题目的意思,一天有两次操作:

沿着一个方向走$k$步,

然后沿着一个方向走到边界。

通过画图呢,我们可以得到大概的图形。

要么在左上角(起点)徘徊,

要么就是路被挡住了,不能徘徊,像蛇形一样往下走了,

要么在右下角(终点)徘徊。

那么要设计三个状态?

不用,因为右下角翻转一下就是左上角,因此只要再照着左上角的徘徊DP方式再做就好了。

于是给出左上角徘徊的定义:

不难发现其实如果要徘徊,一天的结束一定是停在$(i,1)$或$(1,j)$上。

定义状态$f_{i,j,0/1}$表示

0的时候,之前最远达到$i$行,现在要到$(1,j)$的最大价值。

1的时候,之前最远达到$j$列,现在要到$(i,1)$的最大价值。

根据定义有

$f_{i,j,0}=\min\limits\{f_{i-1,j,0},f_{i,j-1,0}+val_{i,j},f_{i-1,j-1,1}+cost_{(i,1)\rightarrow(i,j)\rightarrow(1,j)}\}$

$f_{i,j,1}=\min\limits\{f_{i,j-1,1},f_{i-1,j,1}+val_{i,j},f_{i-1,j-1,0}+cost_{(1,j)\rightarrow(i,j)\rightarrow(i,1)}\}$

然后可以设计一个过渡用的小状态

$L_i,R_i$分别表示停靠在$(i,1),(i,m)$的最优状态。

具体的转移可以参照代码。

之后就过渡到了第二部分:蛇形走位。

分为从$(i-1,1)\rightarrow(i,1)$等四种情况。

考虑一下即可。

之后就是把右下角的状态拼起来就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
using namespace std;
const int N=805,M=N+5;const ull G=31;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
I void cmx(ll &a,ll b){if(a<b)a=b;}
ll col[N][N],row[N][N],f[N][N][2],L[N],R[N],s[N],u[N][2],d[N][2],ans;int val[N][N],n,m,arr[N][N];
void calc()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            col[i][j]=col[i-1][j]+val[i][j],
            row[i][j]=row[i][j-1]+val[i][j];
    memset(f,0xcf,sizeof(f));
    for(int i=1;i<=n;i++)f[i][1][1]=col[i][1],f[i][1][0]=val[1][1];
    for(int i=1;i<=m;i++)f[1][i][1]=val[1][1],f[1][i][0]=row[1][i];
    for(int i=2;i<=n;i++)
        for(int j=2;j<=m;j++)
        {
            ll w=col[i][j]+row[i][j]-val[i][j];
            cmx(f[i][j][0],f[i-1][j][0]);
            cmx(f[i][j][0],f[i-1][j-1][1]+w);
            cmx(f[i][j][0],f[i][j-1][0]+val[1][j]);
            cmx(f[i][j][1],f[i][j-1][1]);
            cmx(f[i][j][1],f[i-1][j-1][0]+w);
            cmx(f[i][j][1],f[i-1][j][1]+val[i][1]);
        }
    memset(L,0xcf,sizeof(L));memset(R,0xcf,sizeof(R));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cmx(L[i],f[i][j][1]);
    for(int i=1;i<=m;i++)s[i]=row[1][m]-row[1][i];
    R[1]=row[1][m];
    for(int i=2;i<=n;i++)
        for(int j=1;j<m;j++)
        {
            s[j]=max(s[j]+val[i][m],col[i][j+1]+row[i][m]-row[i][j+1]);
            cmx(R[i],f[i][j][0]+s[j]);
        }
}
void solve()
{
    memcpy(val,arr,sizeof(val));calc();
    for(int i=1;i<=n;i++)u[i][0]=L[i],u[i][1]=R[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            val[i][j]=arr[n-i+1][m-j+1];
    calc();for(int i=1;i<=n;i++)d[i][0]=R[n-i+1],d[i][1]=L[n-i+1];
    memcpy(val,arr,sizeof(val));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            col[i][j]=col[i-1][j]+val[i][j],
            row[i][j]=row[i][j-1]+val[i][j];
    ll l=0,r=row[1][m-1];
    for(int i=2;i<=n;i++)
    {
        cmx(u[i][0],l+col[i][1]);
        cmx(u[i][1],r+col[i][m]);
        cmx(u[i][0],r+col[i][m]+row[i][m]-val[i][m]);
        cmx(u[i][1],l+col[i][1]+row[i][m]-val[i][1]);
        cmx(l,u[i][0]-col[i][1]);
        cmx(r,u[i][1]-col[i][m]);
    }
    l=row[n][m],r=val[n][m];
    cmx(ans,d[1][0]);
    cmx(ans,u[n][1]);
    for(int i=n-1;i>1;--i)
    {
        l=max(l+val[i][1],d[i][0]);
        r=max(r+val[i][m],d[i][1]);
        cmx(ans,l+u[i-1][0]);
        cmx(ans,r+u[i-1][1]);
    }
}
int main()
{
    qr(n),qr(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            qr(arr[i][j]);
    solve();
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=m;j++)
            swap(arr[i][j],arr[j][i]);
    swap(n,m);
    solve();
    qw(ans);puts("");
    return 0;
}