C++(clang++11) 解法, 执行用时: 4ms, 内存消耗: 400K, 提交时间: 2020-12-08 17:58:26

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=203,M=407;
int h[2][M];
long long v[2][M];
int cnt[2];
int x[110][8];
int q[2][N];
int Find(int cur,int state){
    int t=state%M;
    while(h[cur][t]!=-1&&h[cur][t]!=state)
        if(++t==M) t=0;
    return t;
}

void Insert(int cur,int state,ll w){
    int t=Find(cur,state);
    if(h[cur][t]==-1){
        h[cur][t]=state;
        v[cur][t]=w;
        q[cur][++cnt[cur]]=t;
    }
    else v[cur][t]=max(w,v[cur][t]);
}

int Get(int state,int k){
    return (state>>(k<<1))&3;
}

int Cre(int v,int p){
    return v<<(p<<1);
}

int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&x[i][j]);
        }
    }
    ll maxi=-1e9;
    memset(h,-1,sizeof(h));
    int cur=1;
    Insert(cur,0,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cnt[cur];j++){
            h[cur][q[cur][j]]<<=2;
        }
        for(int j=1;j<=m;j++){
            //cout<<"I "<<i<<" J "<<j<<endl;
            int last=cur;
            cur^=1;
            cnt[cur]=0;
            memset(h[cur],-1,sizeof(h[cur]));
            for(int k=1;k<=cnt[last];k++){
                int state=h[last][q[last][k]];
                ll val=v[last][q[last][k]];
                int l=Get(state,j-1),u=Get(state,j);
                //cout<<"State "<<state<<" "<<val<<" "<<l<<" "<<u;
                if(!l&&!u){
                    if(i<n&&j<m)
                    Insert(cur,state+Cre(1,j-1)+Cre(2,j),val+x[i][j]);
                    Insert(cur,state,val);
                }
                else if(!l){
                    if(j<m)
                    Insert(cur,state,val+x[i][j]);
                    if(i<n)
                    Insert(cur,state-Cre(u,j)+Cre(u,j-1),val+x[i][j]);
                }
                else if(!u){
                    if(i<n)
                    Insert(cur,state,val+x[i][j]);
                    if(j<m)
                    Insert(cur,state-Cre(l,j-1)+Cre(l,j),val+x[i][j]);
                }
                else if(l==1&&u==1){
                    for(int f=j+1,s=1;;f++){
                        int h=Get(state,f);
                        if(h==1) s++;
                        else if(h==2){
                            s--;
                            if(s==0) {
                                Insert(cur,state-Cre(l,j-1)-Cre(u,j)-Cre(1,f),val+x[i][j]);
                                break;
                            }
                        }
                    }
                }
                else if(l==2&&u==1){
                    Insert(cur,state-Cre(l,j-1)-Cre(u,j),val+x[i][j]);
                }
                else if(l==2&&u==2){
                    for(int f=j-2,s=1;;f--){
                        int h=Get(state,f);
                        if(h==2) s++;
                        else if(h==1){
                            if(--s==0){
                                Insert(cur,state-Cre(l,j-1)-Cre(u,j)+Cre(1,f),val+x[i][j]);
                                break;
                            }
                        }
                    }
                }
                else{
                    if((state-Cre(1,j-1)-Cre(2,j))==0)
                        maxi=max(maxi,val+x[i][j]);
                }
            }
        }
    }
    cout<<maxi<<endl;
    return 0;
}