---

其实我觉得这个跟P1004挺类似（又是动规）

 

#include
     
      #include
      
       #include
       
        #define R register intusing namespace std;int n,m;int f[55][55],a[55][55];inline int g(){    R ret=0,fix=1; register char ch;    while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;    do ret=(ret<<3)+(ret<<1)+(ch^48); while(isdigit(ch=getchar()));    return ret*fix;}signed main(){    m=g(),n=g();    for(R i=1;i<=m;i++) for(R j=1;j<=n;j++) a[i][j]=g();    f[1][2]=a[1][2]+a[2][1];    for(R i=4;i<=n+m-1;i++) for(R j=min(i-2,m);j>=1;j--) for(R k=min(i-1,m);k>j;k--) //倒序是为了只访问之前的状态；且令j
        
         1) f[j][k]=max(f[j][k],f[j-1][k]);        if(k-1>j) f[j][k]=max(f[j][k],f[j][k-1]);        if(j>1&&k>1) f[j][k]=max(f[j][k],f[j-1][k-1]);        f[j][k]+=a[j][i-j]+a[k][i-k];    } printf("%d\n",f[m-1][m]);}