题意：
在一个n*m的矩阵中有两只虫子，一只从左上角向右下角移动，另外一只从左下角向右上角移动。
要求：
1.第一只虫子每次只能向左或者向下移动一格，另外一只只能向上或者向右移动一格。
2.两只虫子的路径最多只能重合一点。
3.求解两只虫子路径中除去重合那点其余各点的权值之和最大。
思路：
1.显然这题需要枚举所有可能的相交的点。
2.将问题转化成从四个角向可能的交点的四条路的权值最大。
3.为了保证路径只能有一个交点，我们考虑从可能的交点的上面的点通往上侧的两个角，左面的点通往左侧的两个角以此类推（参考大神的思想）。
4.用递推式子f[i][j]=max(f[i-1][j],f[i][j-1])+map[i][j].（这里只是写了其中一种情况（从左上角到该点的情况，其他三种情况类似））。
坑点：
边界上的点一定不可能作为唯一的交点。
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; int pho[1005][1005]; int pho1[1005][1005]; int pho2[1005][1005]; int pho3[1005][1005]; int pho4[1005][1005]; int main() { int n,m; memset(pho,0,sizeof(pho)); memset(pho1,0,sizeof(pho1)); memset(pho2,0,sizeof(pho2)); memset(pho3,0,sizeof(pho3)); memset(pho4,0,sizeof(pho4)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&pho[i][j]); } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { pho1[i][j]=max(pho1[i-1][j],pho1[i][j-1])+pho[i][j]; } } for(int i=n;i>=1;i--) { for(int j=m;j>=1;j--) { pho2[i][j]=max(pho2[i+1][j],pho2[i][j+1])+pho[i][j]; } } for(int i=n;i>=1;i--) { for(int j=1;j<=m;j++) { pho3[i][j]=max(pho3[i+1][j],pho3[i][j-1])+pho[i][j]; } } for(int i=1;i<=n;i++) { for(int j=m;j>=1;j--) { pho4[i][j]=max(pho4[i-1][j],pho4[i][j+1])+pho[i][j]; } } int ans=-1; bool ok=1; for(int i=2;i<n;i++) { for(int j=2;j<m;j++) { ans=max(ans,pho1[i-1][j]+pho2[i+1][j]+pho3[i][j-1]+pho4[i][j+1]); ans=max(ans,pho1[i][j-1]+pho2[i][j+1]+pho3[i+1][j]+pho4[i-1][j]); } } printf("%d ",ans); }