四维dp了解一下,ok?
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, g[15][15],f[15][15][15][15],i, j, k, l;
int main() {
scanf("%d", &n);
while (1) {
int x, y, v;
scanf("%d%d%d", &x, &y, &v);
g[x][y] = v;
if (!x && !y && !v)
break;
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
for (k = 1; k <= n; k++) {
for (l = 1; l <= n; l++) {
f[i][j][k][l] = max(max(f[i - 1][j][k - 1][l], f[i - 1][j][k][l - 1]), max(f[i][j - 1][k][l - 1],
f[i][j - 1][k - 1][l]))
+ g[i][j] + g[k][l];
if (i == k && j == l)
f[i][j][k][l] -= g[i][j];
}
}
}
}
printf("%d", f[n][n][n][n]);
return 0;
}/*
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
answer:
67
*/
```
by control_our_own_life @ 2023-09-08 23:36:09
这样走两次路径的做法目光短浅，如果有两条路径值相同，dfs只会取一种，取得那一种可能会影响第二次行走，算是局部贪心，所以去看题解上的四位dp吧
by woshidabian @ 2023-09-09 10:27:07