簡單dp，難點在于狀態的表示.
題目可以看做兩人同時取數，這樣就避免了后效性，可以用dp做了.
【狀態】f[i][j][k][l]表示兩人分別到(i,j)、(k,l)所取過的數的和.G[i][j]表示方格里的數.
【方程】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]+(i==k&&j==l ? 0 : G[k][l])
1次WA.
#01: Accepted (75ms, 384KB)
#02: Accepted (0ms, 384KB)
#03: Accepted (0ms, 384KB)
#04: Accepted (28ms, 384KB)
【Code】
1 #include<stdio.h>
2 #include<iostream>
3 using namespace std;
4 int f[12][12][12][12] = {0}, n, G[12][12];
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 a, b, c, i, j, k, l;
13 scanf("%d", &n);
14 for(;;){
15 scanf("%d%d%d", &a, &b, &c);
16 if (a || b || c) G[a][b] = c;
17 else break;
18 }
19 for (i = 1; i <= n; i++)
20 for (j = 1; j <= n; j++)
21 for (k = 1; k <= n; k++)
22 for (l = 1; l <= n; l++){
23 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];
24 if (i == k && j == l) f[i][j][k][l] -= G[i][j];
25 }
26 printf("%d\n", f[n][n][n][n]);
27 }
28