题目链接：http://codeforces.com/problemset/problem/429/B
题意：
给你一个n*m的网格，每个格子上有一个数字a[i][j]。
一个人从左上角走到右下角，一个人从左下角走到右上角，要求两条路径有且仅有一个交点。
问你除去交点格子上的数字，路径上数字之和最大是多少。
题解：
表示状态：
dp[i][j][0/1/2/3] = max sum
表示从某个角走到(i,j)这个格子，最大路径上数字之和
0,1,2,3分别代表左上角、右上角、左下角、右下角
找出答案：
路径相交共有两种方式：
枚举交点(i,j)。
ans = max dp[i-1][j][0] + dp[i+1][j][3] + dp[i][j-1][2] + dp[i][j+1][1]
ans = max dp[i-1][j][1] + dp[i+1][j][2] + dp[i][j-1][0] + dp[i][j+1][3]
如何转移：
四种情况分别算：
（1）dp[i][j][0] = max dp[i-1][j][0]+a[i][j]
dp[i][j][0] = max dp[i][j-1][0]+a[i][j]
（2）dp[i][j][1] = max dp[i-1][j][1]+a[i][j]
dp[i][j][1] = max dp[i][j+1][1]+a[i][j]
（3）dp[i][j][2] = max dp[i+1][j][2]+a[i][j]
dp[i][j][2] = max dp[i][j-1][2]+a[i][j]
（4）dp[i][j][3] = max dp[i+1][j][3]+a[i][j]
dp[i][j][3] = max dp[i][j+1][3]+a[i][j]
边界条件：
set dp = 0
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1005 using namespace std; int n,m;
int a[MAX_N][MAX_N];
int dp[MAX_N][MAX_N][]; void read()
{
cin>>n>>m;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
cin>>a[i][j];
}
}
} void work()
{
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
dp[i][j][]=max(dp[i][j][],dp[i-][j][]+a[i][j]);
dp[i][j][]=max(dp[i][j][],dp[i][j-][]+a[i][j]);
}
}
for(int i=;i<=n;i++)
{
for(int j=m;j>=;j--)
{
dp[i][j][]=max(dp[i][j][],dp[i-][j][]+a[i][j]);
dp[i][j][]=max(dp[i][j][],dp[i][j+][]+a[i][j]);
}
}
for(int i=n;i>=;i--)
{
for(int j=;j<=m;j++)
{
dp[i][j][]=max(dp[i][j][],dp[i+][j][]+a[i][j]);
dp[i][j][]=max(dp[i][j][],dp[i][j-][]+a[i][j]);
}
}
for(int i=n;i>=;i--)
{
for(int j=m;j>=;j--)
{
dp[i][j][]=max(dp[i][j][],dp[i+][j][]+a[i][j]);
dp[i][j][]=max(dp[i][j][],dp[i][j+][]+a[i][j]);
}
}
int ans=;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
ans=max(ans,dp[i-][j][]+dp[i+][j][]+dp[i][j-][]+dp[i][j+][]);
ans=max(ans,dp[i-][j][]+dp[i+][j][]+dp[i][j-][]+dp[i][j+][]);
}
}
cout<<ans<<endl;
} int main()
{
read();
work();
}