#include<bits/stdc++.h>
#define N 105
using namespace std;
int n,m,a[N][N],f[N][N][N];
int max(int a,int b,int c,int d){ // 扩大一下max函数
if(a>=b and a>=c and a>=d)return a;
if(b>=a and b>=c and b>=d)return b;
if(c>=a and c>=b and c>=d)return c;
return d;
}
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >> a[i][j];
}
}
for(int k=1;k<=n+m-2;k++){
for(int i=min(k,n),j=k-i+1;i>=1&&j<=min(k,m);i--,j++){
for(int x=i-1,y=j+1;x>=1&&y<=min(k,m);x--,y++){ // 限制变量
if(y==j+1){ // 两种情况转移
f[k][j][y] = max(f[k-1][j-1][y],f[k-1][j][y],f[k-1][j-1][y-1],-1234567890)+a[i][j]+a[x][y];
}else{
f[k][j][y] = max(f[k-1][j-1][y],f[k-1][j][y-1],f[k-1][j][y],f[k-1][j-1][y-1])+a[i][j]+a[x][y];
}
}
}
}
cout << f[n+m-2][m-1][m] <<endl;
return 0;
}
P1006 [NOIP 2008 提高组] 传纸条
题目大意
给你一个n*m的数字矩阵，你需要从左上到右下走两次，只能向下或向右走，且除了点(1,1)和(n,m)外没有其他路过的点相同。求这种走路方案路过点的权值和最大。
（有点曲解题意但对做题不影响）
提示1
数据量虽然不大（只有50）但显然暴力是不够看的。这里使用动态规划，那么请查看这张图。
题解
如图，我们每次搜索一根最前端的红线的两个不相同的点进行转换。
观察发现：对于每条横线的两个点$(i_1,j_1),(i_2,j_2)$，满足：$i_1+j_i=i_2+j_2$。
红线的数量为：$n+m-1$。
由此，我们可以设$F_{(i,j),(x,y)}$为某条横线上的两个点$(i,j),(x,y)$，即满足$i+j=x+y$且$i
则状态转移方程为：
当两点不在红线上相邻的点时： $$ F_{(i,j),(x,y)} = \max(F_{(i-1,j),(x-1,y)},F_{(i-1,j),(x,y-1)},F_{(i,j-1),(x-1,y)},F_{(i,j-1),(x,y-1)})+A_{i,j}+A_{x,y} $$ 当两点在红线上相邻时：（去掉两点选择相同节点的情况） $$ F_{(i,j),(x,y)} = \max(F_{(i-1,j),(x-1,y)},F_{(i-1,j),(x,y-1)},F_{(i,j-1),(x,y-1)})+A_{i,j}+A_{x,y} $$ 可是这样的四维数组浪费的空间非常大，所以我们直接用一个$k$压掉一维，变成$F_{k,j,y}$，使用$k$计算出$i,x$（当然去掉j、y那两维也可以）：$k+1=i+j=x+y$ => $i=k-j+1,x=k-y+1$。