Codeforces 429B B. Working out dp

题意： 给n*m的矩阵，每个格子有个数，A从(1,1)出发只能向下或右走，终点为(n,m)，B从(n,1)出发只能向上或右走，终点为(1,m)。两个人会在某处相遇，求出除了相遇点外，他们两个路径之和的最大值（相遇点不算作距离） 思路： dp0[I][j]表示从左上角走到(I,j)的最大距离 dp1[I][j]表示从左下角走到(I,j)的最大距离 dp2[I][j]表示从右上角走到(I,j)的最大距离 dp3[I][j]表示从右下角走到(I,j)的最大距离 枚举i，j，由于只能相遇一次 如果A从(I,j-1)进入(I,j)那么只能从(I,j+1)离开(I,j)，B只能从(I+1,j)进入，(I-1,j)离开. 如果A从进入(I-1,j)，那么只能从(I+1,j)离开，B只能从(I,j-1)进入，(I,j+1)离开 这样保证不会有第二次相交

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[4][1010][1010];//0 (1,1)->(i,j) 1 (n,1)  2(1,m) 3 (n,m) 
int matrix[1010][1010];
int main()
{
	int n,m;
	//freopen("in.txt","r",stdin);
	while(cin>>n>>m)
	{
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		cin>>matrix[i][j];
		memset(dp,0,sizeof(dp));
		
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			dp[0][i][j]=max(dp[0][i-1][j],dp[0][i][j-1])+matrix[i][j];
		}
		for(int i=n;i>=1;i--)
		{
			for(int j=1;j<=m;j++)
			dp[1][i][j]=max(dp[1][i+1][j],dp[1][i][j-1])+matrix[i][j];
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=m;j>=1;j--)
			dp[2][i][j]=max(dp[2][i-1][j],dp[2][i][j+1])+matrix[i][j];
		}
		for(int i=n;i>=1;i--)
		{
			for(int j=m;j>=1;j--)
			dp[3][i][j]=max(dp[3][i+1][j],dp[3][i][j+1])+matrix[i][j];
		}
		int ans=0;
		for(int i=2;i<n;i++)
		{
			for(int j=2;j<m;j++)
			{
				ans=max(ans,dp[0][i-1][j]+dp[3][i+1][j]+dp[1][i][j-1]+dp[2][i][j+1]);
				ans=max(ans,dp[0][i][j-1]+dp[3][i][j+1]+dp[2][i-1][j]+dp[1][i+1][j]);
			}
			
		}
		cout<<ans<<endl;
	}
}