题目链接：
http://acm.nyist.net/JudgeOnline/problem.php?pid=712
http://acm.nyist.net/JudgeOnline/problem.php?pid=61
题目大意：
给以个r行，c列的矩阵num[][];要求从矩阵的左上角走到右下角（只能朝右和朝下走），然后从右下角返回左上角（只能朝上和超左），还要求来回不能走重复的路。求满足上述走法的路径上元素之和最大。
思路：
从左上走到右下↘，再从右下走到左上↖,可以看做从左上向右下走两条路↘↘（不相交的路）使得这两条路径上的值加起来最大。
用一个三维的数组来记录，dp[b][x1][x2]，b表示走的步数，表示两条路径上的某个点的横纵坐标相加之和,x1表示第一条路的某一点的横坐标，y1表示第一条路的某一点的横坐标；x2表示第二条路的某一点的横坐标，y2表示第二条路的某一点的横坐标。存在x1+y1=x2+y2=b(2<=b<=r+c)。
只要x1,x2,y1,y2不越界且，y1!=y2就可以保证两条路径无重复点。这两条路径都是从左上走到右下，且只能向下走或者向右走。那么dp[b][x1][x2]=max(dp[b-1][x1][x2]（后退一步时，第一条路和第二条路都是从上面走来的）,
dp[b-1][x1-1][x2-1]（后退一步时，第一条路和第二条路都是从左面走来的）,
dp[b-1][x1-1][x2]（后退一步时，第一条路是从左面走来，第二条路都是从上面走来的）,
dp[b-1][x1][x2-1]（后退一步时，第一条路是上面走来，第二条路都是从左面走来的）,)+num[x1][y1]+num[x2][y2](这两个千万不能忘);
最后，当走终点右下角的时候选择一个较大的路径max(dp[r+c-1][r][r-1],dp[r+c-1][r-1][r])+num[r][c];记得到所求结果,上述两个题目左上和右下角都为0所以就没有加，直接输出了。
AC代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<cstring>
using namespace std;
int num[55][55];
int dp[115][115][115];
int main()
{
int n;
scanf("%d",&n);//n组数据
while(n--)
{
int r,c;
scanf("%d%d",&r,&c);//输入行和列
memset(num,0,sizeof(num));
memset(dp,0,sizeof(dp));
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
scanf("%d",&num[i][j]); //记录每行每列的数
}
}
for(int k=2;k<=r+c;k++)
{
for(int x1=1;x1<=r;x1++)
{
for(int x2=1;x2<=r;x2++)
{
int y1=k-x1;
int y2=k-x2;
if(y2>=1&&y2<=c&&y1>=1&&y1<=c&&y1!=y2)
{
dp[k][x1][x2]+=max(max(dp[k-1][x1-1][x2],dp[k-1][x1][x2-1]),
max(dp[k-1][x1-1][x2-1],dp[k-1][x1][x2]))+num[x1][y1]+num[x2][y2];
}
else
continue;
}
}
}
printf("%d
",max(dp[r+c-1][r][r-1],dp[r+c-1][r-1][r]));
}
return 0;
}