https://ac.nowcoder.com/acm/contest/1041/E
以前从一本通上学的传纸条只会n*m*n*m的
这里又是因为如果我们设走的步数为k，那么只要知道一个点的x坐标，y坐标也能算出来，所以就可以省去一维。
WA了一发，注意x坐标 要<=min(k+1,n)，因为k步最多走到(k+1,1)
#include<bits/stdc++.h> #define maxl 60 using namespace std; int n,m; int a[60][60]; int f[60][60][60][60]; inline void upd(int &x,int y) { if(y>x) x=y; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int x=1;x<=n;x++) for(int y=1;y<=m;y++) if(i==x && j==y) { upd(f[i][j][x][y],f[i-1][j][x-1][y]+a[i][j]); upd(f[i][j][x][y],f[i-1][j][x][y-1]+a[i][j]); upd(f[i][j][x][y],f[i][j-1][x-1][y]+a[i][j]); upd(f[i][j][x][y],f[i][j-1][x][y-1]+a[i][j]); } else { upd(f[i][j][x][y],f[i-1][j][x-1][y]+a[i][j]+a[x][y]); upd(f[i][j][x][y],f[i-1][j][x][y-1]+a[i][j]+a[x][y]); upd(f[i][j][x][y],f[i][j-1][x-1][y]+a[i][j]+a[x][y]); upd(f[i][j][x][y],f[i][j-1][x][y-1]+a[i][j]+a[x][y]); } printf("%d",f[n][m][n][m]); return 0; } #include<bits/stdc++.h> #define maxl 60 using namespace std; int n,m; int a[60][60]; int f[110][60][60]; inline void upd(int &x,int y) { if(y>x) x=y; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); int j,y; for(int k=1;k<=n+m-2;k++) for(int i=1;i<=min(n,k+1);i++) for(int x=1;x<=min(n,k+1);x++) { j=k+2-i;y=k+2-x; if(i==x && j==y) { upd(f[k][i][x],f[k-1][i][x]+a[i][j]); upd(f[k][i][x],f[k-1][i-1][x]+a[i][j]); upd(f[k][i][x],f[k-1][i][x-1]+a[i][j]); upd(f[k][i][x],f[k-1][i-1][x-1]+a[i][j]); } else { upd(f[k][i][x],f[k-1][i][x]+a[i][j]+a[x][y]); upd(f[k][i][x],f[k-1][i-1][x]+a[i][j]+a[x][y]); upd(f[k][i][x],f[k-1][i][x-1]+a[i][j]+a[x][y]); upd(f[k][i][x],f[k-1][i-1][x-1]+a[i][j]+a[x][y]); } } printf("%d",f[n+m-2][n][n]); return 0; }
