题解

题目分析：
这题是中等难度的dp，自行学习够了
代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int m,n,mat[60][60],opt[120][60][60];
int dfs(int p,int x1,int x2){
	int y1=p-x1,y2=p-x2;
	if(x1<0||x1>=m||x2<0||x2>=m) return -1;
	if(y1<0||y1>=n||y2<0||y2>=n) return -1;
	if(p==(m-1)+(n-1)) return 0;
	if(p&&x1==x2) return -1;
	if(opt[p][x1][x2]>=0) return opt[p][x1][x2];
	opt[p][x1][x2]=0;
	for(int v=0;v<4;v++){
		int tmp=dfs(p+1,x1+v%2,x2+v/2);
		if(tmp>opt[p][x1][x2]) opt[p][x1][x2]=tmp;
	} 
	opt[p][x1][x2]+=mat[x1][y1]+mat[x2][y2];
	return opt[p][x1][x2];
}
int main(){
  //freopen("message.in","r",stdin);
  //freopen("message.out","w",stdout); 
	scanf("%d%d",&m,&n);
	for(int i=0;i<m;i++) for(int j=0;j<n;j++) scanf("%d",&mat[i][j]);
	memset(opt,0xff,sizeof(opt));
	printf("%d\n",dfs(0,0,0));
	return 0;
}