code
#include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define LL long long #define Vi vector<int> #define Si set<int> #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) #define FF(i,a) for(int i(0); i < (a); i++) #define FD(i,a) for(int i(a); i >= (1); i--) #define FOR(i,a,b) for(int i(a);i <= (b); i++) #define FOD(i,a,b) for(int i(a);i >= (b); i--) #define PD(a) printf("%d\n",a) #define SET(a,b) memset(a,b,sizeof(a)) #define SD(a) scanf("%d",&(a)) #define LN printf("\n") #define PS printf(" ") #define pb push_back #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const double pi = acos(-1.0); const int maxn = 51; const int INF = 99999999; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; using namespace std; int f[maxn][maxn][maxn][maxn],a[maxn][maxn]; int dp(int x1,int y1,int x2,int y2){ if(f[x1][y1][x2][y2]!=0) return f[x1][y1][x2][y2]; if(x1<1||x2<1||y1<1||y2<1) return f[x1][y1][x2][y2]; int ans=0; ans=max(ans,dp(x1-1,y1,x2-1,y2)); ans=max(ans,dp(x1-1,y1,x2,y2-1)); ans=max(ans,dp(x1,y1-1,x2,y2-1)); ans=max(ans,dp(x1,y1-1,x2-1,y2)); if(x1==x2 && y1== y2) //此处不太明白,是看了别人的解题报告中这么写的, f[x1][y1][x2][y2]=ans+a[x1][y1];//但是明显一个点不能走两次 ,晕 else f[x1][y1][x2][y2]=ans+a[x1][y1]+a[x2][y2]; return f[x1][y1][x2][y2]; } int main(){ // readf; // writef; int M,N; SD(M);SD(N); FOR(i,1,M) FOR(j,1,N) SD(a[i][j]); dp(M,N,M,N); //FOR(i,1,M) FOR(j,1,N) FOR(k,1,M) FOR(l,1,N){ // printf("f[%d][%d][%d][%d]==%d\n",i,j,k,l,f[i][j][k][l]); //} printf("%d\n",f[M][N][M][N]); return 0; }