Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2153 Accepted Submission(s): 1135
题解：多线程dp；
由于从左上到右下再回到左上，可以看成两条线从左上到右下；当x1==x2的时候跳过去；得到：
dp(k, x1, y1, x2, y2) = max(dp(k-1, x1-1, y1, x2-1, y2), dp(k-1, x1-1, y1, x2, y2-1), dp(k-1, x1, y1-1, x2-1, y2), dp(k-1, x1, y1-1,x2, y2-1))
又因为，步数k等于x+y，所以五维化成三维；
得到：
dp(k, x1, x2) = max(dp(k-1, x1, x2), dp(k-1, x1-1, x2), dp(k-1, x1, x2-1), dp(k-1, x1-1, x2-1)) + mp(x1, k-x1) + mp(x2, k-x2) ;
所以得到代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; const int INF=0x3f3f3f3f; #define mem(x,y) memset(x,y,sizeof(x)) #define SI(x) scanf("%d",&x) #define PI(x) printf("%d",x) #define SD(x,y) scanf("%lf%lf",&x,&y) #define P_ printf(" ") typedef long long LL; int mp[50][50],dp[1010][31][31]; int N; int main(){ while(~SI(N)){ for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) SI(mp[i][j]); mem(dp,0); for(int k=3;k<2*N;k++){ for(int x1=1;x1<=N;x1++){ for(int x2=1;x2<=N;x2++){ if(k-x1>N||k-x2>N)continue; if(x1==x2)continue; 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]))+mp[x1][k-x1]+mp[x2][k-x2]; } } } printf("%d\n",max(dp[2*N-1][N][N-1],dp[2*N-3][N-1][N])+mp[N][N]+mp[1][1]); } return 0; }
原文：http://www.cnblogs.com/handsomecui/p/5204497.html