题意：
给定一个 N*M 的矩阵A，每个格子中有一个整数。
现在需要找到两条从左上角 (1,1) 到右下角 (N,M) 的路径，路径上的每一步只能向右或向下走。
路径经过的格子中的数会被取走，两条路径可以经过同一个格子，但格子中的数 只能被取一次。
求取得的数之和最大是多少。
输入格式
第一行有2个用空格隔开的整数n和m，表示矩阵有n行m列。
接下来的n行是一个n*m的矩阵，每行的m个整数之间用空格隔开。
输出格式
输出一个整数，表示答案。
数据范围
1≤n,m≤501≤n,m≤50
输入样例：
3 3
0 3 9
2 8 5
5 7 0
输出样例：
34
题解：
首先考虑路径有交集该如何处理。
可以发现交集中的格子一定在每条路径的相同步数处。因此可以让两个人同时从起点出发，每次同时走一步，这样路径中相交的格子一定在同一步内。
状态表示：f[k, i, j] 表示两个人同时走了k步，第一个人在 (i, k - i) 处，第二个人在 (j, k - j)处的所有走法的最大分值。
状态计算：按照最后一步两个人的走法分成四种情况：
两个人同时向右走，最大分值是 f[k - 1, i, j] + score(k, i, j)；
第一个人向右走，第二个人向下走，最大分值是 f[k - 1, i, j - 1] + score(k, i, j)；
第一个人向下走，第二个人向右走，最大分值是 f[k - 1, i - 1, j] + score(k, i, j)；
两个人同时向下走，最大分值是 f[k - 1, i - 1, j - 1] + score(k, i, j)；
其中如果两人在相同格子，则 score(k, i, j) 等于这个格子的分值；否则等于两个格子的分值之和。
时间复杂度
一共有 O(n3)O(n3) 个状态，每个状态需要 O(1)O(1) 的计算量，因此总时间复杂度是 O(n3)O(n3)。
代码：
#include<iostream> #include<cmath> #include<cstdio> using namespace std; int f[120][60][60]; int n,m; int w[60][60]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&w[i][j]); for(int k=2;k<=n+m;k++) for(int i=max(1,k-m);i<=n&&i<k;i++) for(int j=max(1,k-m);j<=n&&j<k;j++) for(int a=0;a<=1;a++) for(int b=0;b<=1;b++) { int t=w[i][k-i]; if(i!=j)t+=w[j][k-j]; f[k][i][j]=max(f[k][i][j],f[k-1][i-a][j-b]+t); } printf("%d ",f[n+m][n][n]); return 0; }