题意：
在一个n*m的矩阵中有两只虫子，一只从左上角向右下角移动，另外一只从左下角向右上角移动。
要求：
1.第一只虫子每次只能向左或者向下移动一格，另外一只只能向上或者向右移动一格。
2.两只虫子的路径最多只能重合一点。
3.求解两只虫子路径中除去重合那点其余各点的权值之和最大。
思路：
相当于分成四个部分去求各自到达交点的所得到的值，这样才能保证只经过了一个交点；
dp1是从从左上角往中间走，dp2是右下角往中间走，dp3是左下角往中间走，dp4是右上角往中间走；
坑点：
边界上的点一定不可能作为唯一的交点。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn = 1000 + 10; ll a[maxn][maxn]; ll dp1[maxn][maxn]; ll dp2[maxn][maxn]; ll dp3[maxn][maxn]; ll dp4[maxn][maxn]; #define INF 0x3f3f3f3f typedef long long ll; int main() { ll n,m; while( ~ scanf("%I64d%I64d",&n,&m)) { memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); memset(dp3,0,sizeof(dp3)); memset(dp4,0,sizeof(dp4)); for(ll i = 1; i <= n; i ++) { for(ll j = 1; j <= m; j ++) { scanf("%I64d",&a[i][j]); } } for(ll i = 1; i <= n; i ++) { for(ll j = 1; j <= m; j ++) { dp1[i][j] = max(dp1[i -1][j],dp1[i][j - 1]) + a[i][j]; } } for(ll i = n; i >= 1; i --) { for(ll j = m; j >= 1; j --) { dp2[i][j] = max(dp2[i][j + 1],dp2[i + 1][j]) + a[i][j]; } } for(ll i = n; i >= 1; i --) { for(ll j = 1; j <= m; j ++) { dp3[i][j] = max(dp3[i + 1][j],dp3[i][j - 1]) + a[i][j]; } } for(ll i = 1; i <= n; i ++) { for(ll j = m; j >= 1; j --) { dp4[i][j] = max(dp4[i - 1][j],dp4[i][j + 1]) + a[i][j]; } } ll ans = 0; //边界不肯能作为交点 for(ll i = 2; i < n; i ++) { for(ll j = 2; j < m; j ++) { ans = max(ans,dp1[i - 1][j] + dp2[i + 1][j]+dp3[i][j - 1] + dp4[i][j + 1]); ans = max(ans,dp1[i][j - 1] + dp2[i][j + 1] + dp3[i + 1][j] + dp4[i - 1][j]); } } cout << ans << endl; } return 0; }
