要走两次因此，考虑一个四维的数组来实现，然后如果i=k&&j==l的话记得减一次即得到答案。
点击查看代码
#include <iostream>
#include <stack>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>
#include <string.h>
#include <map>
#include <queue>
#include <list>
#include <cmath>
#include <iomanip>
#define int long long
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lc u<<1
#define rc u<<1|1
#define gcd __gcd
#define double long double
#define endl "\n"
#define INF LLONG_MAX
#define mod 1000000007
#define N 15
const double PI = 3.14159265358979323846;
using namespace std;
int dp[N][N][N][N], a[N][N],n;//dp[1][j][k][l]表示第一次和第二次的最优解
signed main()
{
ios;
cin >> n;
while (1)
{
int x, y,z; cin >> x >> y>>z;
if (x == 0 && y == 0&&z==0)break;
a[x][y] = z;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
for (int l = 1; l <= n; l++)
{
dp[i][j][k][l] = max({ dp[i - 1][j][k - 1][l],dp[i][j - 1][k][l - 1],dp[i][j - 1][k - 1][l],dp[i - 1][j][k][l - 1] }) + a[i][j] + a[k][l];
if (i == k && j == l)dp[i][j][k][l] -= a[i][j];
}
}
}
}
cout << dp[n][n][n][n] << endl;
return 0;
}