吐槽

本人感觉题目十分有坑。。。
就是因为没有理解真正的题意。。。

• 两人只能相遇一次
• 从下边上来的人只能从上边出这个点，从左边进来的人只能从右边出这个点

分析

因为我们需要两个人走对角线，并且复杂度允许
所以我们可以直接从4个顶点暴力DP
DP[1/2/3/4][i][j]表示从某个顶点到的最大权值和
求出之后，我们可以直接枚举相遇点
计算到达最终点的权值和最大即可
Res=max(Res,DP[1][X-1][Y]+DP[3][X][Y-1]+DP[2][X][Y+1]+DP[4][X+1][Y]);
Res=max(Res,DP[1][X][Y-1]+DP[3][X+1][Y]+DP[2][X-1][Y]+DP[4][X][Y+1]);
需要注意的一点就是，由于上边吐槽的第二点，我们不能从边界开始走
因为再走一步会直接走出这个GYM

代码

//CF429B
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define LL long long
#define Lowbit(X) (X&(-X))
#define Lson (X<<1)
#define Rson (X<<1|1)
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(int i=A;i<=B;i++)
#define BOR(i,A,B) for(int i=A;i>=B;i--)
#define FOR_SIDE(i,A) for(int i=Head[A];i;i=Next[i])
#define INF 0x7fffffff
using namespace std;
const int MAXN=1e3+10;

int Cube[MAXN][MAXN];
int Row,Line,Ans;
int DP[5][MAXN][MAXN];

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline int Solve(int X,int Y) {
    int Res=0;
    Res=max(Res,DP[1][X-1][Y]+DP[3][X][Y-1]+DP[2][X][Y+1]+DP[4][X+1][Y]);
    Res=max(Res,DP[1][X][Y-1]+DP[3][X+1][Y]+DP[2][X-1][Y]+DP[4][X][Y+1]);
    return Res;
}

int main() {
    //File();
    scanf("%d %d",&Row,&Line);
    FOR(i,1,Row) FOR(j,1,Line) { scanf("%d",&Cube[i][j]); }
    FOR(i,1,Row) FOR(j,1,Line) { DP[1][i][j]=max(DP[1][i-1][j],DP[1][i][j-1])+Cube[i][j]; }
    FOR(i,1,Row) BOR(j,Line,1) { DP[2][i][j]=max(DP[2][i-1][j],DP[2][i][j+1])+Cube[i][j]; } 
    BOR(i,Row,1) FOR(j,1,Line) { DP[3][i][j]=max(DP[3][i+1][j],DP[3][i][j-1])+Cube[i][j]; }
    BOR(i,Row,1) BOR(j,Line,1) { DP[4][i][j]=max(DP[4][i+1][j],DP[4][i][j+1])+Cube[i][j]; }
    FOR(i,2,Row-1) FOR(j,2,Line-1) { Ans=max(Ans,Solve(i,j)); }
    printf("%d\n",Ans);
    //fclose(stdin); fclose(stdout);
    system("pause");
    return 0;
}