和2000的方格取数如出一辙.数据加强了一点，如果是裸的四维dp可能会超时(80).所以需要优化.
1.普通的四维做法
【状态】f[x1][y1][x2][y2] 表示从出发点分别到(x1,y1)、(x2,y2)取的最大值.G[x][y]表示该格的数.
【方程】f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2],f[x1][y1-1][x2][y2-1]}+G[x1][y1]+G[x2][y2](如果位置不重复)
【一个重要优化】显然有y2=x1+y1-x2(y2>0),因而时间复杂度可以降到O(n^3).Cena显示总用时从近4s降到近0.3s，效果明显.
2.三维做法(参考官方题解)
【状态】f[p][x1][x2],p表示经过的格子数.
【方程】f[p][x1][x2]=max{f[p-1][x1-1][x2-1],f[p-1][x1-1][x2],f[p-1][x1][x2-1],f[p-1][x1][x2]}+G[x1][p-x1]+G[x2][p-x2](如果位置不重复)
未编程验证.
3.更优化的做法
dy神牛指出，进一步的优化需要用到最小费用最大流.(NOIP绝对超纲,可以确定不会更深了.)
【Code】
1 #include<stdio.h>
2 #include<iostream>
3 using namespace std;
4 int f[52][52][52][52] = {0}, n, G[52][52];
5 int max(int a, int b, int c, int d){
6 if (a < b) a= b;
7 if (a < c) a= c;
8 if (a < d) a= d;
9 return a;
10 }
11 int main(){
12 int m, n, i, j, k, l;
13 scanf("%d%d", &m, &n);
14 for (i = 1; i <= m; i++)
15 for (j = 1; j <= n; j++)
16 scanf("%d", &G[i][j]);
17 for (i = 1; i <= m; i++)
18 for (j = 1; j <= n; j++)
19 for (k = 1; k <= m; k++){
20 if (i+j-k > 0) l = i+j-k; else continue;
21 f[i][j][k][l] = max(f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1])+G[i][j]+G[k][l];
22 if (i == k && j == l) f[i][j][k][l] -= G[i][j];
23 }
24 printf("%d\n", f[m][n][m][n]);
25 }
26