题目链接：http://codeforces.com/problemset/problem/429/B
题目大意：两个人（假设为A，B），打算健身，有N行M列个房间，每个房间能消耗Map[i][j]的卡路里，A起点为（1,1）要达到（n,m）点，且每次只能向右走一步或向下走一步，
B起点为（n,1），要达到（1，m），且每次只能向上走一步，或向右走一步。有要求A,B必须在某一个房间相遇一次，且A,B在该房间不再消耗卡路里，因为两人锻炼身体的速度不同，
所以在相遇时经过的房间数亦可能不相同。问两人合计最多消耗多少卡路里。
解题思路：
先预处理四个dp数组：
dp1[i][j]表示从(1,1)到(n,m)路程中,(1,1)到(i,j)的最优解
dp2[i][j]表示从(1,1)到(n,m)路程中,(i,j)到(n,m)的最优解
dp3[i][j]表示从(n,1)到(1,m)路程中,(n,1)到(i,j)的最优解
dp4[i][j]表示从(n,1)到(1,m)路程中,(i,j)到(1,m)最优解
由于两人只能相遇一次，若两人相遇则肯定会是以下两种情况（蓝色表示A可能经过的区域，红色表示B可能经过的区域，紫色为相遇点）：
那么对应上图两种情况分别有：
t1=dp1[i][j-1]+dp2[i][j+1]+dp3[i+1][j]+dp4[i-1][j];//情况一
t2=dp1[i-1][j]+dp2[i+1][j]+dp3[i][j-1]+dp4[i][j+1];//情况二
所以我们只要枚举点（i,j）即可，注意1<i<n且1<j<n否则不符合上图的情况。
代码：
#include<bits/stdc++.h>
#define lc(a) (a<<1)
#define rc(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define _for(i,start,end) for(int i=start;i<=end;i++)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long LL;
const int N=1e3+;
const int INF=0x3f3f3f3f;
const double eps=1e-; int mp[N][N];
LL dp1[N][N],dp2[N][N],dp3[N][N],dp4[N][N]; int main(){
FAST_IO;
int n,m;
cin>>n>>m;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++)
cin>>mp[i][j];
}
//计算从(1,1)到(n,m)路程中,(1,1)到(i,j)的最优解
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
dp1[i][j]=max(dp1[i-][j],dp1[i][j-])+mp[i][j];
}
}
//计算从(1,1)到(n,m)路程中,(i,j)到(n,m)的最优解
for(int i=n;i>=;i--){
for(int j=m;j>=;j--){
dp2[i][j]=max(dp2[i+][j],dp2[i][j+])+mp[i][j];
}
}
//计算从(n,1)到(1,m)路程中,(n,1)到(i,j)的最优解
for(int i=n;i>=;i--){
for(int j=;j<=m;j++){
dp3[i][j]=max(dp3[i+][j],dp3[i][j-])+mp[i][j];
}
}
//计算从(n,1)到(1,m)路程中,(i,j)到(1,m)最优解
for(int i=;i<=n;i++){
for(int j=m;j>=;j--){
dp4[i][j]=max(dp4[i-][j],dp4[i][j+])+mp[i][j];
}
} LL ans=-;
//枚举相遇点,注意不能在边界相遇，因为这样两个人相遇肯定不止一次
for(int i=;i<n;i++){
for(int j=;j<m;j++){
LL t1=dp1[i][j-]+dp2[i][j+]+dp3[i+][j]+dp4[i-][j];//情况一
LL t2=dp1[i-][j]+dp2[i+][j]+dp3[i][j-]+dp4[i][j+];//情况二
ans=max(ans,max(t1,t2));
}
}
cout<<ans<<endl;
return ;
}